算法模板之二分查找
目录
二分查找应用于在有序数组中寻找满足特定条件的元素,时间复杂度可以降到O(logn)
,该算法的必要前提是有序数组必须有序。
查找不小于target元素的下标
int lower_bound(int[] nums, int start, int end, int target) {
int mid = 0;
while (start < end) {
mid = (start + end) / 2;
if (target > nums[mid]) {
start = mid + 1;
} else {
end = mid;
}
}
if (nums[end] < target) return -1;
return end;
}
查找大于target元素的下标
int upper_bound(int[] nums, int start, int end, int target) {
int mid = 0;
while (start < end) {
mid = (start + end) / 2;
if (target >= nums[mid]) {
start = mid + 1;
} else {
end = mid;
}
}
if (nums[end] < target) return -1;
return end;
}
查找第一个target元素的下标
int exist_bound(int[] nums, int start, int end, int target) {
int mid = 0;
while (start < end) {
mid = (start + end) / 2;
if (target > nums[mid]) {
start = mid + 1;
} else if (target < nums[mid]) {
end = mid - 1;
} else {
if (mid - 1 < 0) {
return 0;
} else if (nums[mid - 1] == target) {
end = mid - 1;
} else {
return mid;
}
}
}
if (end < 0 || nums[end] != target) return -1;
return end;
}
历史评论
开始评论