二分查找及其应用

Classical Binary Search

经典二分查找适用于不包含重复元素的有序数组。二分查找每次取中间值，然后和目标值比较。若中间值大于目标值，则表示目标值在前半部分，反之则在后半部分。然后重复上述过程，直到找到目标值位置，或者遍历所有元素。

代码如下：

#！/usr/bin/env python3
# -*- coding utf-8 -*-
"""
    @param: nums: An integer array sorted in ascending order
    @param: target: An integer
    @return: An integer
"""
def binarySearch(nums,target):
    if len(nums) == 0:#数组为空
        return -1
    start = 0
    end = len(nums)-1
    while start <= end:
        # mid = (start+end)//2
        mid = (start+end)>>1#除2
        if nums[mid]>target:
            end = mid-1
        elif nums[mid]<target:
            start = mid+1
        else:
            return mid
     return -1

当我第一次写时，将 while 循环中的条件设为 start<end ，实际运行发现某些情况会进入死循环。当数组中不包含目标值时，最后变量之间的关系为 start+1=end mid=start ,所以会一直在 while 中循环，无法跳出。

First Position of Target

问题：

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1
在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2

因为数组中有重复元素，所以发现目标值时并不能直接返回。当发现中间值时与目标值相等时，有两种情况：

中间值正好是首次出现，也就是说重复的目标值都在中间值后面而不是前面

如 1223 第一次取中间值正好取到 2 ，此时元素位置为 1，正好满足要求

中间值前面还有重复的目标值

如 12223 第一次取中间值时同样为 2，元素位置为 2，但是这并不是 2 第一次出现的位置。

因此，当发现中间值与目标值相等时，我们默认为上文中的第 2 中情况，也就是说将 end = mid ，当循环完成时，需要进行二次判断，首先判断 start ，然后判断 end ,因为 start 和 end 位置的元素都有可能与目标值相等。

代码如下：

def binarySearch(nums,target):
    if len(nums) == 0:
        return -1
    start = 0
    end = len(nums)-1
    while start<=end:
        mid = (start+end)>>1
        if nums[mid]>=target:
            end = mid-1
        else:
            start = mid+1
    if nums[start] == target:
        return start
    if nums[end] == target:
        return end
    return -1

Last Position of Target

问题：给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target最后一次出现的下标（从0开始），如果target不存在于数组中，返回-1
在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回3

这个问题与上个类似，当找到一个数与目标值相等时，只需查找后半段是否还有满足题意的数，将 start = mid 。最后先判断 end 位置的数，然后再判断 start 位置。

代码如下：


def binarySearch(nums,target):
    if len(nums)==0:
        return -1
    start = 0
    end = len(nums)-1
    while start<=end:
        mid = (start+end)>>1
        if nums[mid]<=target:
            start = mid+1
        else:
            end = mid-1
    if nums[end] == target:
        return end
    if nums[start] == target:
        return start
    return -1

Closest Number in Sorted Array

问题：

在一个有序数组中，给定一个target，要求在数组中找到离target最近的数。

Given [1, 4, 6] and target = 3, return 1.

Given [1, 4, 6] and target = 5, return 1 or 2.

Given [1, 3, 3, 4] and target = 2, return 0 or 1 or 2.

先使用经典二分查找 target，最后再判断距离最近的数

代码如下：

def closetNumber(nums, target):
    if len(nums) == 0:
        return -1
    start = 0
    end = len(nums) - 1
    while start  <= end:
        mid = (start + end) >> 1
        if nums[mid] > target:
            end = mid-1
        elif nums[mid] < target:
            start = mid+1
        else:
            return mid
    left = abs(nums[start]-target)#判断start与target的距离
    right = abs(nums[end]-target)
    return start if left<right else end

Total Occurrence of Target

问题：

求有序数组中某个target出现了多少次

利用 Python 内置函数直接判断：

1 2	def totalOccurrence(nums,target): return nums.count(target)

利用二分法，先查找 target 第一次出现的位置，然后从第一次出现的位置开始遍历列表。

def totalOccurance(nums,target):
    if len(nums) == 0:
        return -1
    start = 0
    end = len(nums)-1
    while start+1<end:
        mid = (start+end)>>1
        if nums[mid]>=target:
            end = mid
        else:
            start = mid
     if nums[start] == target:
        count = 0
        for i in nums[start:len(nums)-1]
            if i == target:
                count+=1
        return count
     if nums[end] == target:
        count = 0
        for i in nums[end:len(nums)-1]:
            if i == target:
                count+=1
        return count

以上所有源代码链接：https://github.com/ianxin/Algorithm/tree/master/src

参考资料

LintCode二分查找题总结