二分查找及各类变体

这篇文章是复习过程中，对二分查找的一个总结。其实二分查找的思想很简单，但是可以生发出的各种细节变化却很多，所以每次写的时候都感觉自己的思路不是非常清晰，主要参考的是https://github.com/ZXZxin/ZXBlog/blob/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95/Algorithm/BinarySearch/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E7%9A%84%E6%80%BB%E7%BB%93(6%E7%A7%8D%E5%8F%98%E5%BD%A2).md。
本文变体主要指：1、找到一个xxx，2、找到最后一个xxx，3、先减后增或先增后减数组找最小或最大。

二分查找原始形式

经典二分：顺序排列，数字不重复，需要注意的是此时的while条件是left<=right，需要注意区间的开闭。

def binaryorigin(array,target):
    left = 0
    right = len(array)-1
    while left <= right:
        mid = left + (right-left)/2
        if array[mid] == target:
            return mid
        elif array[mid]>target:
            #中间比target大，目标在左边
            right = mid-1
        else:
            #中间比target小，目标在右边
            left = mid +1
    return -1
testarray = [1,2,3,4]
print binaryorigin(testarray,1),binaryorigin(testarray,4),binaryorigin(testarray,5)

结果为 0 3 -1

变体1：有重复值的数组，找到第一个=target的位置

此时并不是目标大于target才right-1，等于也要减，因为我们找的是第一个等于target的位置。

def binary1(array,target):
    left = 0
    right = len(array)-1
    while left <= right:
        mid = left+(right-left)/2
        if array[mid] >= target:
            right = mid-1
        else:
            left = mid +1
    #判断等于target且没有越界
    if array[left] == target and left <= len(array)-1:
        return left
    return -1
test1 = [1,2,3,3,3,3,4,5]
binary1(test1,3)

输出为2

变体2:有重复，找到第一个大于等于target的位置

比第一个等于相当于不需要判断等于和,如果不存在的话，需要判断一下left的位置，否则会返回数组长度，而不是最后一个位置。

def binary2(array,target):
    left = 0
    right = len(array)-1
    while left <= right:
        mid = left+(right-left)/2
        if array[mid] >= target:
            right = mid-1
        else:
            left = mid +1
    if left >= len(array)-1:
        left = len(array)-1
    return left
test2 = [1,2,3,3,3,3,4,5]
print binary2(test1,3),binary2(test1,10)

输出为2 7

变体3 第一个大于target的位置

需要改动的是判断array[mid]>target

def binary3(array,target):
    left = 0
    right = len(array)-1
    while left <= right:
        mid = left+(right-left)/2
        if array[mid]>target:
            right = mid-1
        else:
            left = mid +1
    #没找到比target大的，返回-1
    if left >= len(array):
        return -1
    return left
test2 = [1,2,3,3,3,3,4,5]
print binary3(test2,3),binary3(test2,5),binary3(test2,0)

输出为6 -1 0

变体4:找到最后一个等于target的位置，没有就返回-1

和变体1不同的是，我们返回的是right，而且在找的时候mid<=target的时候都要去左边寻找。

def binary4(array,target):
    left = 0
    right = len(array)-1
    while left<=right:
        mid = left+(right-left)/2
        if array[mid]<=target:
            left = mid +1
        else:
            right = mid -1
    if array[right] == target and right <= len(array)-1:
        return right
    return -1
test2 = [1,2,3,3,3,3,4,5]
print binary4(test2,3),binary4(test2,5),binary4(test2,0)

结果为5 7 -1

变体5 找到最后一个小于等于target的位置

不同的是不需要判断array[right]==target，如果array元素都比target小的话就是
#返回最后一个元素，所有都比target大就返回-1

def binary5(array,target):
    left = 0
    right = len(array)-1
    while left<= right:
        mid = left + (right-left)/2
        if array[mid]<= target:
            left = mid +1
        else:
            right = mid-1
    return right
test2 = [1,2,3,3,3,3,4,5]
print binary5(test2,3),binary5(test2,4.5),binary5(test2,0)

输出5 6 -1

变体6：找到最后小于一个target的位置

判断array[mid]<target

def binary6(array,target):
    left = 0
    right = len(array)-1
    while left<= right:
        mid = left + (right-left)/2
        if array[mid]< target:
            left = mid +1
        else:
            right = mid -1
    return right
test2 = [1,2,3,3,3,3,4,5]
print binary6(test2,3),binary6(test2,4.5),binary6(test2,0)

输出 1 6 -1

变体7：驼峰数组，先增后减

和正常的二分法的退出条件不同，此时的退出条件是mid的边界，因为后面有减一加一的，所以需要在（0，len-1）之间。

tuo = [1,2,3,4,5,3,1]
def binary7(array):
    left = 0
    right = len(array)-1
    mid = left + (right-left)/2
    while mid > 0 and mid < len(array)-1:
        if array[mid] >  array[mid+1] and array[mid] > array[mid - 1]:
            return mid
        #处在上升段
        elif array[mid] < array[mid+1]:
            left = mid +1
            mid = left + (right-left)/2
        #处在下降段
        else:
            right = mid -1
            mid = left + (right-left)/2
    return -1
binary7(tuo)

输出 4

变体8:凹陷数组，先减后增

ao = [5,3,2,1,4]
def aoxian(array):
    left = 0
    right = len(array)-1
    mid = left + (right-left)/2
    while mid > 0 and mid < len(array)-1:
        if array[mid]<array[mid+1] and array[mid]<array[mid-1]:
            return mid
        #处在下降段
        elif array[mid]> array[mid+1]:
            left = mid +1
            mid = left + (right-left)/2
        else:
            right = mid +1
            mid = left + (right-left)/2
    return -1
aoxian(ao)

输出 3

变体9：旋转数组

原本为[1,2,3,4,5,6]旋转后变为[5,6,1,2,3,4]，两部分有序数组。

#旋转数组最小数字，最小数字的特点是比前一个数字小。
x = [6,1,2,3,4,5]
def xuanzhuan(array):
    left = 0
    right = len(array)-1
    #非旋转数组
    if array[left]<array[right]:
        return array[left]
    mid = left+(right-left)/2 
    while left<right:
        mid = left+(right-left)/2
        print mid,left,right
        if array[mid] < array[mid -1]:
            return array[mid]
        #中间比右边大的时候，说明最小数字应该在现在mid的右边，所以left右移
        if array[mid] > array[right]:
            left = mid + 1
        elif array[mid] == array[right]:
            #与右边一样则right左移一位
            right = right -1
        else:
            #比右边小说明现在在第二个区间里面，而且此时mid不满足比前一个小，所以right右移到前面
            right = mid
          
    return array[left]
xuanzhuan(x)

输出
2 0 5
1 0 2
1

总结

1. 找最后一个xxx的时候，用的是小于／小于等于的判断，先处理的是left，输出right。等于的时候需要判断边界条件，其余不需要。
2. 找第一个xxx的时候，用的是大于／大于等于的判断，先处理right，再处理left，最后输出的是left，等于的时候也要判断边界。
3. 是部分有序数组时，退出条件不同，需要判断的是目前所处位置数字和前后数字之间的大小关系，判断其处于上升还是下降阶段，再进行向左向右的处理。