二分查找类算法题

 

 

 

二分查找基本模版：

def two_find(nums, target ,l ,r):
    if l>r: return False
    m = (l+r)//2
    if nums[m]==target:
        return True
    elif nums[m] < target:
        return two_find(nums, target, m+1, r)
    elif nums[m] > target:
        return two_find(nums, target, l, m-1)

def two_find2(nums,target):
    l,r = 0, len(nums)-1
    while l<=r:
        m = (l+r)//2
        if nums[m]==target: return True
        elif nums[m]<target:    l = m+1
        else : r = m-1
    return False

if __name__ == '__main__':
    nums = [1,5,7,8,9,12,16,19,23]
    target = 4
    target = 23
    r = two_find(nums, target, 0, len(nums)-1)
    # r = two_find2(nums, target)
    print(r)

33. 在旋转数组中查找元素

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

方法思路：
1.根据 首尾判断是否旋转
2.若未旋转，直接二分查找（注意：可以直接判断target是否在首尾之内，否则直接返回-1）
3.若旋转， 先找旋转点（以找到最大值为例）
（1）情况一：target在[0,index_max]之内：此范围二分查找
（2）情况二：target在[index_max+1,len(nums)-1]之内：此范围二分查找
（3）情况三：若不在以上两种情况则直接返回-1

class Solution:
    def search(self, nums, target):
        if len(nums)<1: return -1
        # 二分查找
        def two_find(l,r):
            if l>r: return -1
            m = (l+r)//2
            if nums[m]==target: return m
            elif nums[m]>target: return two_find(l,m-1)
            else: return two_find(m+1,r)

        # 寻找最大的 max_index 值
        def find_max(l,r):
            m = (l+r)//2
            if nums[m]>nums[m+1]: return m
            elif nums[m]>nums[0]: return find_max(m+1,r)
            else : return find_max(l,m-1)

        # 正常的升序数组
        if nums[len(nums)-1]>nums[0]:
            return two_find(0,len(nums)-1)
        else:
            max_index = find_max(0,len(nums)-1)
            if nums[max_index]>=target and target>=nums[0]: return two_find(0,max_index)
            elif target>=nums[max_index+1] and target<nums[-1]:return two_find(max_index+1,len(nums)-1)
            else: return -1


    from typing import List
    def search2(self, nums: List[int], target: int) -> int:
        if len(nums) < 1: return -1
        if len(nums) == 1:
            return 0 if nums[0] == target else -1

        # 二分查找
        def two_find(l, r):
            while l <= r:
                m = (l + r) // 2
                if nums[m] == target:
                    return m
                elif nums[m] < target:
                    l = m + 1
                else:
                    r = m - 1
            return -1

        def find_max(nums):
            l, r = 0, len(nums) - 1
            while l <= r:
                m = (l + r) // 2
                if m != len(nums) - 1 and nums[m] > nums[m + 1]:
                    return m
                elif nums[0] <= nums[m]:
                    l = m + 1
                else:
                    r = m - 1
            return len(nums) - 1

        max_id = find_max(nums)
        # print(max_id)
        if target <= nums[max_id] and target >= nums[0]:
            res = two_find(0, max_id)
        else:
            res = two_find(max_id + 1, len(nums) - 1)
        return res

 

34.在排序数组中查找元素的 第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。
找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
--------------------------------------------------------------------------------
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

class Solution:
    def searchRange(self, nums, target):
        # 二分查找--左边界
        def find_left(l ,r):
            if l> r: return -1
            m = (l + r) // 2
            if (target == nums[m] and m == 0) or (target == nums[m] and target != nums[m - 1]):
                return m
            elif target < nums[m] or (target == nums[m] and target == nums[m - 1]):
                return find_left(l, m - 1)
            else:
                return find_left(m + 1, r)

        # 查找最右边界 index
        def find_right(l, r):
            if l > r: return -1
            m = (l + r) // 2
            if (target == nums[m] and m == len(nums) - 1) or (target == nums[m] and target != nums[m + 1]):
                return m
            elif target > nums[m] or (target == nums[m] and target == nums[m + 1]):
                return find_right(m + 1, r)
            else:
                return find_right(l, m - 1)

        if len(nums) == 0: return [-1, -1]
        if target >= nums[0] and target <= nums[-1]:
            left = find_left(0, len(nums) - 1)
            if left == -1: return [-1, -1]
            if left == len(nums) - 1 or nums[left + 1] != target:
                return [left, left]
            else:
                right = find_right(left + 1, len(nums) - 1)
                return [left, right]
        else:
            return [-1, -1]


if __name__=="__main__":
    s=Solution()
    nums=[1]
    target=1
    r = s.searchRange(nums,target)
    print(r)