前提
类型
- 查询一个数字所在位置
- 查询左侧边界,查询目标数字最先出现的位置,第一个大于目标数字的位置
查询右侧边界,查询目标数字最后出现的位置,第一个小于目标数字的位置
细节关键点
查询区间是否开闭
- 边界情况,mid节点靠前还是靠后 r是len(nums) 还是 len(nums)-1 (取决于是否开闭区间)
- 跳出条件 是l<r 还是 l<=r
- l r 移动是 l = mid 还是 l=mid+1 (取决于是否开闭区间)
框架
```go // 1 全部采用闭区间查询 // 2 因为闭区间查询,mid节点靠前 l,r := 0, len(numid节点靠前,闭区间查询ms)-1
// 3 因为mid节点靠前,可能出现l=m=l+1的情况,所以l<=r // 但是如果是查询边界,需要在最后再检查是否超出 // 4 因为闭区间查询 l = mid+1 闭区间
//三种情况区别 //1 nums[m] == target 时,指针移动或者return //2 值查找 return m 边界查找 l=m+1 或者 r=m-1 //3 值查找 return -1 func binarySearch(nums []int,int target)int{ l,r := 0, len(nums)-1 for l<=r { m := l+(r-l)/2 //防止溢出 if num[m] < target { l = m + 1 }else nums[m] > target { r = m - 1 }else { return m //如果是寻找边界,则不能返回,要靠近边界,直到搜索完成 //左侧边界 r = m - 1 //右侧边界 l = m + 1 } } return -1 //由于最后一轮可能是l==r情况下的处理,则l,r可能会超出 所以需要判断是否超出 //查询左侧边界的情况 // if l > len(nums)-1 || nums[l]!=target { // return -1 // } // return l //查询右侧边界的情况 // if r < 0 || nums[r]!=target { // return -1 // } // return r
}
```go
// 查找目标数
func binarySearch(nums []int,int target)int{
l,r := 0, len(nums)-1
for l<=r {
m := l+(r-l)/2 //防止溢出
if num[m] < target {
l = m + 1
}else nums[m] > target {
r = m - 1
}else {
return m
}
}
return -1
}
// 查找左侧边界