二分查找【python总结】

作者: 惊不意外 | 来源:发表于2019-05-15 19:59 被阅读0次

双指针（链表、数组）
二分查找【python总结】
算法之二分查找
python二分查找
Python实现二分法
算法图解系列之二分查找[01]
基础算法笔记 python和C++
算法之二分查找
算法
LeetCode 专题：数组

将原本是线性时间提升到了对数时间log(N)范围，大大缩短了搜索时间

前提，必须在有序数据中进行查找。

1. 最基本的二分查找

leetcode参考[35]：Search Insert Position

剑指offer：数字在排序数组中出现的次数

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

其中，有几个要注意的点：

循环的判定条件是：low <= high
为了防止数值溢出，mid = low + (high - low)/2
当 A[mid]不等于target时，high = mid - 1或low = mid + 1

2. 查找目标值区域的边界

Leetcode参考[34]: Find First and Last Position of Element in Sorted Array

剑指offer：数字在排序数组中出现的次数

2.1 查找目标值区域的左边界/查找与目标值相等的第一个位置/查找第一个不小于目标值数的位置

A = [1,3,3,5, 7 ,7,7,7,8,14,14]
target = 7
return 4

def binarySearchLowerBound(A,  target):
    low,high = 0,len(A)-1
    while low <= high:
        mid = low + (high - low) // 2
        if target <= A[mid]:
            high = mid - 1
        else:
            low = mid + 1
    if low < A.length and A[low] == target:
        return low
    else
        return -1

2.2 查找目标值区域的右边界/查找与目标值相等的最后一个位置/查找最后一个不大于目标值数的位置

A = [1,3,3,5,7,7,7, 7 ,8,14,14]
target = 7
return 7

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

此题以可变形为查找第一个大于目标值的数/查找比目标值大但是最接近目标值的数，我们已经找到了最后一个不大于目标值的数，那么再往后进一位，返回high + 1，就是第一个大于目标值的数。

2.3 查找最后一个小于目标值的数/查找比目标值小但是最接近目标值的数

此题以可由第 2 题变形而来，我们已经找到了目标值区域的下（左）边界，那么再往左退一位，即low - 1，就是最后一个小于目标值的数。其实low - 1也是退出循环后high的值，因为此时 high刚好等于low - 1，它小于low，所以 while 循环结束。我们只要判断high是否超出边界即可。

A = [1,3,3, 5 ,7,7,7,7,8,14,14]
target = 7
return 3

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

2.4 查找第一个大于目标值的数/查找比目标值大但是最接近目标值的数

此题以可由第 3 题变形而来，我们已经找到了目标值区域的上（右）边界，那么再往右进一位，即high + 1，就是第一个大于目标值的数。其实high + 1也是退出循环后low的值，因为此时 low刚好等于high + 1，它大于high，所以 while 循环结束。我们只要判断low是否超出边界即可。

A = [1,3,3,5,7,7,7,7, 8 ,14,14]
target = 7
return 8

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

3. 在旋转数组中查找最小元素

3.1 查找旋转数组的最小元素（假设不存在重复数字）

LeetCode[153]: Find Minimum in Rotated Sorted Array
Input: [3,4,5,1,2]
Output: 1

def findMin(nums):
    if len(nums) == 0
        return -1
    left,right = 0,len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

注意这里和之前的二分查找的几点区别：

循环判定条件为left < right，没有等于号
循环中，通过比较nums[left]与num[mid]的值来判断mid所在的位置:

如果nums[mid] > nums[right]，说明前半部分是有序的，最小值在后半部分，令left = mid + 1；
如果nums[mid] <= num[right]，说明最小值在前半部分，令right = mid。

最后，left会指向最小值元素所在的位置。

3.2 查找旋转数组的最小元素（存在重复项）

LeetCode[154]: Find Minimum in Rotated Sorted Array II
剑指offer：旋转数组的最小数字
Input: [2,2,2,0,1]
Output: 0

def findMin(nums):
    if len(nums) == 0
        return -1
    left,right = 0,len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        elif nums[mid] < nums[right]:
            right = mid
        else:
            right-=1
    return nums[left]

和之前不存在重复项的差别是：当nums[mid] == nums[right]时，我们不能确定最小值在 mid的左边还是右边，所以我们就让右边界减一。

4. 在旋转排序数组中搜索

4.1 在旋转排序数组中搜索并返回目标元素的下标（不考虑重复项）

LeetCode[33]: Search in Rotated Sorted Array

法一：

先利用方法 3.1 查找数组中的最小元素，即确定分界点的位置
把旋转的数组当成偏移，用(offset + mid) % len来求真实的 mid 的位置。
然后用二分查找来定位目标值

def search(self, nums: List[int], target: int) -> int:
    lo,hi=0,len(nums)-1
    while lo<hi:
        mid=(lo+hi)//2
        if nums[mid]>nums[hi]:
            lo=mid+1
        else:
            hi=mid 
    offset =lo #lo==hi is the index of the smallest value
    lo,hi=0,len(nums)-1
    while lo<=hi:
        mid=lo+(high-lo)//2
        realmid=(mid+offset)%len(nums)
        if nums[realmid]==target:
            return realmid
        if nums[realmid]<target: 
            lo=mid+1
        else:
            hi=mid-1
    return -1

法二：其实没有必要找到旋转数组的分界点，对于搜索左侧还是右侧我们是可以根据mid跟high的元素大小来判定出来的，直接根据target的值做二分搜索就可以了。

def search(self, nums: List[int], target: int) -> int:
    if len(nums) == 0:
        return -1
    left,right=0,len(nums)-1
    while left<=right:
        mid=left+(right-left)//2
        if nums[mid] == target:
            return mid
        elif nums[left] <= nums[mid]:
            if target < nums[mid] and target >= nums[left]:
                right = mid - 1
            else:
                left = mid + 1
        elif nums[mid] <= nums[right]:
            if target > nums[mid] and target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

4.2 在旋转排序数组中搜索并返回目标元素的下标（考虑重复项）

LeetCode: Search in Rotated Sorted Array II

def search(self, nums: List[int], target: int) -> int:
    if len(nums) == 0:
        return -1
    left,right=0,len(nums)-1
    while left<=right:
        mid=left+(right-left)//2
        if nums[mid] == target:
            return mid
        elif nums[mid] > nums[right]:
            if target < nums[mid] and target >= nums[left]:
                right = mid 
            else:
                left = mid + 1
        elif nums[mid] < nums[right]:
            if target > nums[mid] and target <= nums[right]:
                left = mid + 1
            else:
                right = mid
        else:
            right-=1
    return -1