几个比较常用的二分查找场景：在排序数组里寻找一个数、寻找一个数的左侧边界、寻找一个数的右侧边界。
找值
在有序数组中找某一个值 有就返回索引 没有返回-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;找左右边界：
在一个排序数组中找到某个数的左边界和右边界，如果没有则返回-1.
左边界和右边界正好是对称的，找左边界的时候 如果相等是收缩右边界，同时看结果是依据左边界对应的值。
而找右边界的时候 如果和target相等则是收缩左边界，看结果是依据右边界对应的值。
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = searchLeftBorder(nums, target);
int right = searchRightBorder(nums, target);
return new int[]{left, right};
}
int searchLeftBorder(int[] nums, int target){
int l = 0, r = nums.length-1;
while(l <= r){
int mid = l + (r - l)/2;
if(nums[mid] >= target){
r = mid - 1;
}else{
l = mid + 1;
}
}
return l < nums.length && nums[l] == target ? l : -1;
}
int searchRightBorder(int[] nums, int target){
int l = 0, r = nums.length-1;
while(l <= r){
int mid = l + (r - l)/2;
if(nums[mid] > target){
r = mid - 1;
}else{
l = mid + 1;
}
}
return r >= 0 && nums[r] == target ? r :-1;
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/92805.html
