前提

有序数组

类型

  1. 查询一个数字所在位置
  2. 查询左侧边界,查询目标数字最先出现的位置,第一个大于目标数字的位置
  3. 查询右侧边界,查询目标数字最后出现的位置,第一个小于目标数字的位置

    细节关键点

  4. 查询区间是否开闭

  5. 边界情况,mid节点靠前还是靠后 r是len(nums) 还是 len(nums)-1 (取决于是否开闭区间)
  6. 跳出条件 是l<r 还是 l<=r
  7. 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

}

  1. ```go
  2. // 查找目标数
  3. func binarySearch(nums []int,int target)int{
  4. l,r := 0, len(nums)-1
  5. for l<=r {
  6. m := l+(r-l)/2 //防止溢出
  7. if num[m] < target {
  8. l = m + 1
  9. }else nums[m] > target {
  10. r = m - 1
  11. }else {
  12. return m
  13. }
  14. }
  15. return -1
  16. }
  17. // 查找左侧边界