二分查找思路非常简单，但是变种比较多，在这些变种中，尤其边界条件特别容易出错（特别是在追求完美简洁的代码的时候）。以下就是一个寻找第一个等于特定值的元素的简洁实现：

1
2
3
4
5
6
7
8
9
10
11
12
def find_first_equal(arr, target):
  left = 0
  right = len(arr) - 1
  while left <= right:
    mid = (left + right) // 2
    if arr[mid] >= target:
      right = mid - 1
    else:
      left = mid + 1
  if left < len(arr) and arr[left] == target:
    return left
  return -1

虽然以上的代码非常简洁，但是理解起来却非常烧脑。如果只是死记硬背上面的解法，过不了几天就会全部忘光，再次编写的时候还是 90% 的概率会出错。相比而言下面的解法就容易理解的多！并且能非常好处理二分查找问题的几个变种！

查找第一个等于特定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def find_first_equal(arr, target):
  left = 0
  right = len(arr) - 1
  while left <= right:
    mid = (left + right) // 2
    if arr[mid] < target:
      left = mid + 1
    elif arr[mid] > target:  
      right = mid - 1
    else:
      if mid == 0 or arr[mid - 1] != target:
        return mid
      right = mid - 1  
  return -1

查找最后一个等于特定值的元素

我们几乎不需要改动大的代码流程，只需要在相等的那个判断中稍微改下即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
def find_last_equal(arr, target):
  left, right = 0, len(arr) - 1
  while left <= right:
    mid = (left + right) // 2
    if arr[mid] < target:
      left = mid + 1
    elif arr[mid] > target:
      right = mid - 1
    else:
      if mid == len(arr) - 1 or arr[mid + 1] != target:
        return mid
      left = mid + 1   
  return -1

查找第一个大于等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
def find_first_greater_equal(arr, target):
  left, right = 0, len(arr) - 1
  while left <= right:
    mid = (left + right) // 2
    if arr[mid] >= target:
      if mid == 0 or arr[mid - 1] < target:
        return mid
      right = mid - 1
    else:
      left = mid + 1
  return -1

查找最后一个小于等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
def find_last_less_equal(arr, target):
  left, right = 0, len(arr) - 1
  while left <= right:
    mid = (left + right) // 2
    if arr[mid] <= target:
      if mid == len(arr) - 1 or arr[mid + 1] > target:
        return mid
      left = mid + 1  
    else:
      right = mid - 1
  return -1