二分查找

1. 口诀

1.1 类型1 左侧查找型

对于从小到大排序的数组，查找第一个>= target 的元素
比如

index: 0 1 2 3 4 5 6
value: 1 2 3 3 5 6 7

查找第一个大于等于3的数字，mid=3, 满足条件， 但是答案是2，相当于在满足条件的情况下，继续向左侧查找
需要的解，向左侧查找。

left=0
// 如果返回len(array)，表示没有找到，如果一定有解，那么设置为len(array)-1
right=len(array)
for left<right {
  mid=(left+right)/2
  if array[mid]>=target {
    // mid位置的元素满足条件，mid有可能是解，也有可能解在左侧，所以right=mid
    right=mid
  }else{
    // mid位置的元素小于target，那么解一定在右侧(且一定不包含mid)，因此调节左边界
    left=mid+1
  }
  return right
}

1.2 类型2 右侧查找型

对于从小到大排序的数组，查找最后一个<= target 的元素
比如

index: 0 1 2 3 4 5 6
value: 1 2 2 3 3 6 7

查找最后一个小于等于3的数字，mid=3, 满足条件， 但是答案是4，相当于在满足条件的情况下，继续向右侧查找
需要的解，向右侧查找。

// 如果返回-1，表示没有找到，如果一定有解，可以设置为0
left=-1
right=len(array)-1
for left<right {
  mid=(left+right+1)/2
  if array[mid]<=target {
    // mid位置的元素满足条件，mid有可能是解，也有可能解在右侧，所以left=mid
    left=mid
  }else{
    // mid位置的元素大于target，那么解一定在左侧(且一定不包含mid)，因此调节左边界
    right=mid-1
  }
  return right
}

2. 口诀

2.1 类型1 左侧查找型

对于从小到大排序的数组，查找第一个>= target 的元素
比如

index: 0 1 2 3 4 5 6
value: 1 2 3 3 5 6 7

查找第一个大于等于3的数字，mid=3, 满足条件， 但是答案是2，相当于在满足条件的情况下，继续向左侧查找
需要的解，向左侧查找。

left=0
right=len(array)-1
for left<right {
  mid=(left+right)/2
  if array[mid]>=target {
    // mid位置的元素满足条件，mid有可能是解，也有可能解在左侧，所以right=mid
    right=mid
  }else{
    // mid位置的元素小于target，那么解一定在右侧(且一定不包含mid)，因此调节左边界
    left=mid+1
  }
  if array[right]!=target{
    return -1
  }
  return right
}

2.2 类型2 右侧查找型

对于从小到大排序的数组，查找最后一个<= target 的元素
比如

index: 0 1 2 3 4 5 6
value: 1 2 2 3 3 6 7

查找最后一个小于等于3的数字，mid=3, 满足条件， 但是答案是4，相当于在满足条件的情况下，继续向右侧查找
需要的解，向右侧查找。

left=0
right=len(array)-1
for left<right {
  mid=(left+right+1)/2
  if array[mid]<=target {
    // mid位置的元素满足条件，mid有可能是解，也有可能解在右侧，所以left=mid
    left=mid
  }else{
    // mid位置的元素大于target，那么解一定在左侧(且一定不包含mid)，因此调节左边界
    right=mid-1
  }
  if array[right]!=target{
    return -1
  }
  return right
}

3. 例题

153. 寻找旋转排序数组中的最小值
154. 寻找旋转排序数组中的最小值 II
34. 在排序数组中查找元素的第一个和最后一个位置