二分查找 #
1、有序数组,查找一个数搜索一个数,如果存在,返回其索引,否则返回 -1。 #
int binarySearch(vector<int>& nums, int target) { int left = 0;
int right = nums.size() - 1; // 注意
while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
else if(nums[mid] == target)
return mid;
}
return -1;
}
1、为什么 while 循环的条件中是 <=,而不是 <? #
答:因为初始化right的赋值是nums.length - 1,每次进行搜索的区间,相当于两端都闭区间[left, right]。while 循环什么时候应该终止?搜索区间为空的时候应该终止,意味着你没得找了,就等于没找到嘛。
while(left <= right)的终止条件是left == right + 1,写成区间的形式就是[right + 1, right],这时候区间为空,所以这时候 while 循环终止是正确的,直接返回 -1 即可。
while(left < right)的终止条件是left == right,写成区间的形式就是[right, right],或者带个具体的数字进去[2, 2],这时候区间非空,还有一个数 2,但此时 while 循环终止了。也就是说这区间[2, 2]被漏掉了,索引 2 没有被搜索,如果这时候直接返回 -1 就是错误的。
2、为什么left = mid + 1,right = mid - 1?我看有的代码是right = mid或者left = mid,没有这些加加减减,到底怎么回事,怎么判断? #
答:本算法的搜索区间是两端都闭的,即[left, right]。那么当我们发现索引mid不是要找的target时,下一步应该去搜索哪里呢?当然是去搜索[left, mid-1]或者[mid+1, right]对不对?因为mid已经搜索过,应该从搜索区间中去除。
3、此算法有什么缺陷? #
答:比如说给你有序数组nums = [1,2,2,2,3],target为 2,此算法返回的索引是 2,没错。但是如果我想得到target的左侧边界,即索引 1,或者我想得到target的右侧边界,即索引 3,这样的话此算法是无法处理的。这样的需求很常见,你也许会说,找到一个 target,然后向左或向右线性搜索不行吗?可以,但是不好,因为这样难以保证二分查找对数级的复杂度了。
2、有序数组,寻找左侧边界 #
int left_bound(int[] nums, int target) { int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else{
right = mid - 1;
}
}
// 检查出界情况
if (left >= nums.size() || nums[left] != target)
return -1;
return left;
}
1、为什么 while 中是<而不是<=? #
答:每次循环的「搜索区间」是[left, right)左闭右开。 while(left < right)终止的条件是left == right,此时搜索区间[left, left)为空,所以可以正确终止。
2、如果nums中不存在target这个值,怎么办? #
左侧边界的特殊含义:nums中小于 target 的元素有 left 个。
3、为什么left = mid + 1,right = mid?和之前的算法不一样? #
答:这个很好解释,因为我们的「搜索区间」是[left, right)左闭右开,所以当nums[mid]被检测之后,下一步的搜索区间应该去掉mid分割成两个区间,即[left, mid)或[mid + 1, right)。
4、为什么该算法能够搜索左侧边界? #
答:关键在于对于nums[mid] == target这种情况的处理。找到 target 时不要立即返回,而是缩小「搜索区间」的上界right,在区间[left, mid)中继续搜索,即不断向左收缩,达到锁定左侧边界的目的。
3、有序数组,寻找右侧边界 #
int right_bound(int[] nums, int target) { int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (right < 0 || nums[right] != target)
return -1;
return right;
}