我们有三种方式可以使用二分查找
1.朴素的二分查找，这种方式可能存在局限性
2.查找左边界的二分查找
3.查找右边界的二分查找
1.二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
这个题我们用朴素的二分查找模板
当我们有一个数组num
定义left=0，right=num.length-1 我们找到中心点mid=left+（right-left）/2
1.当num[mid]<target 说明mid左边都比target小 left=mid+1
2.当num[mid]>target 说明mid右边都比target大 right=mid-1
3.找到时就返回下标，没找到时就返回-1
代码如下
class Solution {
public int search(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 return mid;
}
return -1;
}
}2.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0 输出：[-1,-1]
代码原理
这种情况下我们找左端点和右端点是不一样的
分为两种情况
左端点：
假如有如图所示的一个数组，我们在数组分成两个区间，一个小于T，一个大于等于T
这时我们把mid=left+（right-left）/2
当nums[mid]>=T时 这是区间里有可能也有t 我们就让right=mid
当nums[mid]<T时 这时区间里都是比t小的 我们就让left =mid+1
最终left和right重合的地方就是我们要找的左端点
右端点：
如图所示，我们把数组分成小于等于t的和大于t的
这时我们把mid=left+（right-left+1）/2
当nums[mid]>T时 这是区右边区间里都比t大 我们就让right=mid-1
当nums[mid]<=T时 这时区间里可能也有t 我们就让left =mid
最后left和right重合的位置就是右端点的值
代码如图
package erfen;
public class searchRange {
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret=new int[2];
ret[0]=ret[1]=-1;
if(nums.length==0) return ret;//处理空数组情况
//处理左端点
int left=0,right=nums.length-1;
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]<target)left=mid+1;
else right=mid;
}
if(nums[left]!=target)return ret;
else ret[0]=right;
//处理右端点
left=0;right=nums.length-1;
while(left<right){
int mid=left+(right-left+1)/2;
if(nums[mid]<=target) left=mid;
else right=mid-1;
}
if(nums[right]!=target)return ret;
else ret[1]=left;
return ret;
}
}
}
