微信 网站,休闲文化网站,网站优化是往新闻中心发新闻吗,住房和城乡建设局是干什么的翻了一下自己的博客。记录了花花酱的二分搜索模板、王争的二分搜索模板。 花花酱的文章中提到#xff1a;不要试图去找一个正确答案。试图去找一个分割点m#xff0c;使得xm#xff0c;g(x)0为true。这个始终get不到。 王争的二分模板思路是比较简单的#xff0c;就…翻了一下自己的博客。记录了花花酱的二分搜索模板、王争的二分搜索模板。 花花酱的文章中提到不要试图去找一个正确答案。试图去找一个分割点m使得xmg(x)0为true。这个始终get不到。 王争的二分模板思路是比较简单的就是时间长了忘记了。考虑边界值的时候是在代码逻辑中考虑容易理解。
接下来记录一下labuladong的二分搜索模板。
1 查找目标值
简单二分查找目标值。
int binarySearch(int[] nums, int target) {int left 0; int right nums.length - 1; // 注意while(left right) {int mid left (right - left) / 2;if(nums[mid] target)return mid; else if (nums[mid] target)left mid 1; // 注意else if (nums[mid] target)right mid - 1; // 注意}return -1;
}2 查找目标值的左边界
查找目标值的左边界也就是第一个等于目标值的位置。
int left_bound(int[] nums, int target) {int left 0, right nums.length - 1;// 搜索区间为 [left, right]while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {// 搜索区间变为 [mid1, right]left mid 1;} else if (nums[mid] target) {// 搜索区间变为 [left, mid-1]right mid - 1;} else if (nums[mid] target) {// 收缩右侧边界right mid - 1;}}// 检查出界情况,因为退出条件是leftright1if (left nums.length || nums[left] ! target)return -1;return left;
}左侧边界的含义是数组中target的数有多少个取值区间是[0,nums.length]
如果targetnums中的任何元素那么在整个搜索过程中right会不断变小left0所以此时退出条件是right-1。因为该方法中返回的是left所以不需要检查边界。 如果targetnums中的任何元素那么在个搜索过程中left会不断变大所以此时的退出条件是leftnums.length。因为该方法中返回的是left这个时候left会越界所以需要检查。
3 查找目标值的右边界
查找目标值的右边界也就是最后一个等于目标值的位置。
int right_bound(int[] nums, int target) {int left 0, right nums.length - 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) {// 这里改成收缩左侧边界即可left mid 1;}}// 这里改为检查 right 越界的情况见下图if (right 0 || nums[right] ! target)return -1;return right;
}因为当nums[mid] target的时候修改的是left那退出循环的时候left指向的可能nums[left]不等于target所以检测right。 那这个时候right一定指向nums[right]target吗
