二分查找-Python刷题笔记

二分搜索是一种在有序数组中查找某一特定元素的搜索算法。

二分查找示意图
搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

Leetcode 二分查找题目列表

查找特定元素

• 利用递归实现

# 返回 x 在 arr 中的索引，如果不存在返回 -1
def binarySearch (arr,l,r, x): 

    # 基本判断
    if r >= l: 
        mid = l + (h-l)//2 # 中部

        if arr[mid] == x: 
            return mid 
        elif arr[mid] > x: 
            return binarySearch(arr, l, mid-1, x) 
        else: 
            return binarySearch(arr, mid+1, r, x)   
    else: 
        return False
  
# 测试
arr = [ 2, 3, 4, 10, 40 ] 
x = 10
result = binarySearch(arr,0,len(arr)-1, x) 
  
if result: 
    print ("元素在数组中的索引为 %d" % result )
else: 
    print ("元素不在数组中")

• 循环实现

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

arr = [ 2, 3, 4, 10, 40 ] 
x = 10
result = binarySearch(arr, x) 
  
if result: 
    print ("元素在数组中的索引为 %d" % result )
else: 
    print ("元素不在数组中")

面试题11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]
输出：1

详解二分查找

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        l, r = 0, len(numbers)-1
        while l <= r:
            mid = (l+r)//2
            if numbers[mid] > numbers[r]:
                l = mid + 1
            elif numbers[mid] < numbers[r]:
                r = mid
            else:
                r -= 1
        return numbers[l]

image

• numbers[mid] > numbers[r]
  mid 目前处于左排序数组。也就是说旋转点在mid右侧的区间 [mid+1, r]
• numbers[mid] < numbers[r]
  mid 目前处于右排序数组 ，即旋转点一定在mid左侧的区间 [l, m]
• numbers[mid] = numbers[r]
  判断不了mid位置
  [1, 0, 1, 1, 1]：旋转点 x = 1 ，m=2 在 右排序数组 中。
  [1, 1, 1, 0, 1]：旋转点 x = 3 ，m=2 在 左排序数组 中。
  r -= 1 缩小范围

33. 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。

找到中点值 MID， 它的左侧或者右侧必有一侧为有序数列。

# 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
# ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
# 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
# 你可以假设数组中不存在重复的元素。
# 你的算法时间复杂度必须是 O(log n) 级别。

def search(nums, target):
    numslength = len(nums)
    l,h = 0, numslength
    while l<h:
        m = (l+h)//2
        if nums[m] == target:
            return m
        elif nums[m] < target:
            if nums[l] == target:
                return l
            elif nums[l] < nums[m]: # 左侧有序,不在左侧
                l = m + 1
            elif nums[l] > nums[m]: # 左侧无序，右侧有序
                if target < nums[l]:
                    l = m + 1
                elif target > nums[l]:
                    h = m - 1
        elif nums[m] > target:
            if nums[l] == target:
                return l
            elif nums[l] < nums[m]: # 左侧有序,在左侧
                if target < nums[l]:
                    l = m + 1
                elif target > nums[l]:
                    h = m
            elif nums[l] > nums[m]: # 左侧无序，右侧有序
                h = m - 1
    return -1

x = search([4,5,6,7,0,1,2],3)
print(x)

超时
优化，合并判断条件

def search(nums, target):
    l,h = 0, len(nums)
    while l<h:
        m = (l+h)//2
        if nums[m] == target:
            return m
        elif nums[l] == target:
            return l
        elif nums[m] < target:
            if target > nums[l] > nums[m]:
                h = m
            else:
                l = m + 1
        elif nums[m] > target:
            if target < nums[l] < nums[m]:
                l = m + 1
            else:
                h = m
    return -1

x = search([4,5,6,7,0,1,2],3)
print(x)

---

1095. 山脉数组中查找目标值

交互式问题
给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
如果不存在这样的下标 index，就请返回 -1。

• A.length >= 3
• 0 < i < A.length - 1 条件下
  • A[0] < A[1] < ... A[i-1] < A[i]
  • A[i] > A[i+1] > ... > A[A.length - 1]

# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        
        arr_len = mountain_arr.length()
        l,r = 0, arr_len-1
        mount_peak_index = 0
        #   找峰顶 mount_peak_index
        while l < r:
            m = (l+r) // 2

            ml_val = mountain_arr.get(m-1)
            mr_val = mountain_arr.get(m+1)
            m_val = mountain_arr.get(m)
            
            if ml_val < m_val and mr_val < m_val:
                mount_peak_index = m
                break   
            elif ml_val < m_val < mr_val:
                l = m
            elif ml_val > m_val > mr_val:
                r = m

        # 要找等于 target 最小的下标, 先查左侧
        # 峰顶左侧，递增序列二分查找
        l,r = 0,mount_peak_index
        while l <= r:
            m = (l+r) // 2
            m_val = mountain_arr.get(m)
            if m_val == target:
                return m
            elif m_val > target:
                r = m-1
            elif m_val < target:
                l = m+1
        
        # 峰顶右侧，递减序列二分查找
        l,r = mount_peak_index,arr_len-1
        while l <= r:
            m = (l+r) // 2
            m_val = mountain_arr.get(m)
            if m_val == target:
                return m
            elif m_val > target:
                l = m+1
            elif m_val < target:
                r = m-1
        
        return -1

---

Reference

[1] Python 二分查找
[2] 二分查找【python总结】
[3] 面试题11. 旋转数组的最小数字（二分法，清晰图解）
[4]Leetcode 二分查找题目列表