二分查找

适合场景

  • 二分查找依赖的是顺序表结构，简单点说就是数组
  • 二分查找针对的是有序数据。
  • 数据量太小不适合二分查找。
  • 数据量太大也不适合二分查找。


写二分算法的注意点

  • 循环退出条件
  • mid 的取值（防止溢出）
  • low 和 high 的更新


程序

  • 循环写法

    1. from typing import List
    2. # 循环写法
    3. def binary_search(nums: List[int], target: int) -> int:
    4.   """
    5.   nums:一个数字列表
    6.   target：目标值
    7.   return：目标值在列表中的索引，
    8.   """
    9.   if len(nums) == 0:
    10.       return -1
    11.   low = 0
    12.   high = len(nums)-1 
    13.   while low<=high: # 小于等于
    14.       mid = low + ((high-low) >> 1) # 取整，移位更高效，防止溢出
    15.       if nums[mid] == target:
    16.           return mid
    17.       elif nums[mid] > target:
    18.           high = mid-1 # 
    19.       elif nums[mid] < target:
    20.           low = mid+1 # 
    21.   return -1

  • 递归写法

    1. from typing import List
    2. # 循环写法
    3. def binary_search(nums: List[int],low: int, high: int, target: int) -> int:
    4.   if low > high:
    5.       return -1
    6.   mid = low + ((high-low) >> 1) # 取整，移位更高效，防止溢出
    7.   if nums[mid] == target:
    8.       return mid
    9.   elif nums[mid] > target:
    10.       return binary_search(nums, low, mid-1, target)
    11.   elif nums[mid] < target:
    12.       return binary_search(nums, mid+1, high, target)

    二分查找的变形

查找算法 - 图1

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

如果 mid 等于 0，那这个元素已经是数组的第一个元素，那它肯定是我们要找的；如果 mid 不等于 0，但 a [mid] 的前一个元素 a [mid-1] 不等于 value，那也说明 a [mid] 就是我们要找的第一个值等于给定值的元素。

  1. from typing import List
  2. # 循环写法
  3. def binary_search(nums: List[int], target: int) -> int:
  4.     if len(nums) == 0:
  5.         return -1
  6.     low = 0
  7.     high = len(nums)-1 
  8.     while low<=high: # 小于等于
  9.         mid = low + ((high-low) >> 1) # 取整，移位更高效，防止溢出
  10.         if nums[mid] > target:
  11.             high = mid-1 # 
  12.         elif nums[mid] < target:
  13.             low = mid+1 # 
  14.         else:
  15.             if (mid==0) or (nums[mid-1] != target):
  16.             # mid-1 代表往前找，mid=0 说明已经是第一个元素了
  17.                 return mid
  18.             else:
  19.                 high = mid - 1
  20.     return -1

往前一直找

  1. from typing import List
  2. # 循环写法
  3. def binary_search(nums: List[int], target: int) -> int:
  4.     if len(nums) == 0:
  5.         return -1
  6.     low = 0
  7.     high = len(nums)-1 
  8.     while low<=high: # 小于等于
  9.         mid = low + ((high-low) >> 1) # 取整，移位更高效，防止溢出
  10. #         print(mid)
  11.         if nums[mid] == target:
  12.             while nums[mid-1] == target:
  13.                 mid -= 1
  14.             return mid
  15.         elif nums[mid] > target:
  16.             high = mid-1 # 
  17.         elif nums[mid] < target:
  18.             low = mid+1 # 
  19.     return -1

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

from typing import List
# 循环写法
def binary_search(nums: List[int], target: int) -> int:
    if len(nums) == 0:
        return -1
    low = 0
    high = len(nums)-1 
    while low<=high: # 小于等于
        mid = low + ((high-low) >> 1) # 取整，移位更高效，防止溢出
        if nums[mid] > target:
            high = mid-1 # 
        elif nums[mid] < target:
            low = mid+1 # 
        else:
            # mid+1 代表往后找，mid=len(nums)-1 说明已经是最后一个元素了
            if (mid==len(nums)-1) or (nums[mid+1] != target):
                return mid
            else:
                low = mid + 1
    return -1

往后面去找

from typing import List
# 循环写法
def binary_search(nums: List[int], target: int) -> int:
    if len(nums) == 0:
        return -1
    low = 0
    high = len(nums)-1 
    while low<=high: # 小于等于
        mid = low + ((high-low) >> 1) # 取整，移位更高效，防止溢出
#         print(mid)
        if nums[mid] == target:
            while nums[mid+1] == target:
                mid += 1
            return mid
        elif nums[mid] > target:
            high = mid-1 # 
        elif nums[mid] < target:
            low = mid+1 # 
    return -1

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

from typing import List
# 循环写法
def binary_search(nums: List[int], target: int) -> int:
    if len(nums) == 0:
        return -1
    low = 0
    high = len(nums)-1 
    while low<=high: # 小于等于
        mid = low + ((high-low) >> 1) # 取整，移位更高效，防止溢出
        if nums[mid] >= target:
            if ((mid == 0) or (nums[mid - 1] < target)):
                return mid;
            else:
                high = mid - 1
        elif nums[mid] < target:
            low = mid+1 # 
    return -1

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


from typing import List
# 循环写法
def binary_search(nums: List[int], target: int) -> int:
    if len(nums) == 0:
        return -1
    low = 0
    high = len(nums)-1 
    while low<=high: # 小于等于
        mid = low + ((high-low) >> 1) # 取整，移位更高效，防止溢出
        if nums[mid] > target: 
            high = mid - 1
        else:
            if (mid==len(nums)-1) or nums[mid+1] > target:
                return mid
            else:
                low = mid+1 # 
    return -1

相关题目

语雀内容