二分查找

第一篇二分查找的论文在1946年就发表了,但是第一个没有错误的二分查找程序却直到1962年才出现。关于二分查找,主要有以下三个问题:

  1. 二分查找元素target(可能有重复)的下标,若不存在,则返回-1。如果元素有重复,则任意返回其中的一个。
  2. 二分查找元素target(可能有重复)第一次出现的下标,若不存在,则返回-1。
  3. 二分查找元素target(可能有重复)最后一次出现的下标,若不存在,则返回-1。

对于问题1,我们只需要用最原始的二分查找即可。Python代码如下:

def binarySearch(nums,target):
    low = 0
    high = len(nums) - 1
    while low <= high: 
        mid = (low + high) // 2 
        if target > nums[mid]:
            low = mid + 1
        elif target < nums[mid]:
            high = mid - 1
        else:
            return mid
    return -1

代码第4行中必须是小于等于号,如果是小于号,会找不到边界值。

对于问题2,我们只需要找到target重复出现情况下的第一次出现的下标。我们只需要用nums[mid]和元素target比较,当target>nums[mid]时,此时待查元素一定在区间的右半部分,且不包括mid。所以有low=mid+1。当target<=nums[mid]时,有high=mid。直到low==high时终止循环,并比较nums[low]是否为target,若是,则找到,返回low。否则未找到,返回-1。Python代码如下:

def binarySearch(nums,target):
    low = 0
    high = len(nums) - 1
    while low < high: 
        mid = (low + high) // 2 
        if target > nums[mid]:
            low = mid + 1
        else:
            high = mid
    if nums[low] == target:
        return low
    return -1

对于问题3,我们只需要找到target重复出现情况下的最后一次出现的下标。和问题2的一个区别是,这里while的条件是low+1<high。接下来的while内部情况和问题2类似。Python代码如下:

def binarySearch(nums,target):
    low = 0
    high = len(nums) - 1
    while low + 1 < high:
        mid = (low + high) // 2
        if target < nums[mid]:
            high = mid - 1
        else:
            low = mid
    if nums[high] == target:
        return high
    elif nums[low] == target:
        return low
    return -1

2 thoughts on “二分查找

  1. Pingback: LeetCode Search for a Range | nce3xin_code

  2. Pingback: LeetCode Search in Rotated Sorted Array | nce3xin_code

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.