算法模板之二分查找
目录
二分查找应用于在有序数组中寻找满足特定条件的元素,时间复杂度可以降到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;
}
本文由「黄阿信」创作,创作不易,请多支持。
如果您觉得本文写得不错,那就点一下「赞赏」请我喝杯咖啡~
商业转载请联系作者获得授权,非商业转载请附上原文出处及本链接。
关注公众号,获取最新动态!
历史评论
开始评论