二分查找方法 leetcode题

这里用来记录使用二分查找方法的题目

1. 704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间

解法1: 二分查找必须注重细节：（1）： <= or < （2）： + 1 or -1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right: # 查找的区间为闭区间，所以要等号，保证数据都被查找过， 小于等于结束条件： left=end+1, 
            # mid = left + (right-left) // 2 # 和 mid = (left+right)//2  一样
            mid = (left+right) // 2 
            if nums[mid] == target:
                break
            elif nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1  # 验证过mid 所以可以 +1或-1
        # 加补丁
        return mid if nums[mid] == target else -1

解法2: 不加补丁

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right: # 查找的区间为闭区间，所以要等号，保证数据都被查找过， 小于等于结束条件： left=end+1, 
            # mid = left + (right-left) // 2 # 和 mid = (left+right)//2  一样
            mid = (left+right) // 2 
            if nums[mid] == target:
                return mid  # 找到就返回
            elif nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1  # 验证过mid 所以可以 +1或-1
        return -1

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [], target = 0
输出：[-1,-1]

解法1: 二分查找，分别找最左侧，和右侧的

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1, -1]
        def binarySearch_left(nums, target): # 找最左侧的
            left = 0
            right = len(nums) - 1
            ans = -1 # 多使用一个变量
            while left <= right:
                mid = left + (right - left) // 2
                # 找左边的
                if nums[mid] == target:
                    ans = mid
                    right = mid - 1 # 继续往左找， 已经记录下了找到过的位置，不怕丢
                elif nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
            return ans if 0<=ans <len(nums) and nums[ans]==target else -1
        left = binarySearch_left(nums, target)   

        def binarySearch_right(nums, target):  #  找最右侧的
            left = 0
            right = len(nums) - 1
            ans = -1 # 用来记录 
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:  # 换成 常规写法
                    left = mid + 1
                elif nums[mid] == target:  # 只能找到 相等
                    ans = mid    # 这种思路，简单容易想， 并且和常规二分相同， 可以用
                    left = mid + 1  # 相等了， 继续 left 右移动， 来 判断右边还有没有
                elif nums[mid] > target:
                    right = mid - 1 
            # ans 可能没找到 
            return ans if 0 <= ans < len(nums) and nums[ans]==target else -1
        right = binarySearch_right(nums, target)
        return [left, right]

3. 面试题 10.03. 搜索旋转数组

搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。

示例1:

 输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
 输出: 8（元素5在该数组中的索引）

示例2:

 输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
 输出：-1 （没有找到）

提示:

arr 长度范围在[1, 1000000]之间

解法1: 遍历O(n)

解法2: 二分查找，（面试遇到这个题，没搞出）

class Solution:
    def search(self, arr: List[int], target: int) -> int:
        # 比较  注意细节
        left = 0
        right = len(arr) - 1
        while left < right:  # 若使用 <=:  最后需加判断条件：0 <= left < len(arr)
            mid = (left + right) // 2
            # 注意比较的条件: 是比较 arr[left] 和 arr[mid] 而不是 left和mid
            if arr[left] < arr[mid]:  # 左边是升序
                if arr[left] <= target <= arr[mid]: # target在左边
                    right = mid  # 不是mid-1
                else:  # target在右边
                    left = mid + 1
            elif arr[left] > arr[mid]: # 左边不是升序
                if arr[left] <= target or target <= arr[mid]: # 值在左边
                    right = mid
                else:  # target在右边
                    left = mid + 1
            else: # 即 arr[left] == arr[mid]
                if arr[left] == target:
                    # 找到 索引最小的了
                    break
                else:
                    left += 1  # left+1 从左逐个比较 
        # print(left)
        # if arr[left] == target:  # if else 
        #     return left
        # return -1
        return left if arr[left] == target else -1

4. 668. 乘法表中第k小的数

几乎每一个人都用乘法表。但是你能在乘法表中快速找到第k小的数字吗？

给定高度m 、宽度n 的一张 m * n的乘法表，以及正整数k，你需要返回表中第k 小的数字。

例 1：

输入: m = 3, n = 3, k = 5
输出: 3
解释: 
乘法表:
1	2	3
2	4	6
3	6	9

第5小的数字是 3 (1, 2, 2, 3, 3).

例 2：

输入: m = 2, n = 3, k = 6
输出: 6
解释: 
乘法表:
1	2	3
2	4	6

第6小的数字是 6 (1, 2, 2, 3, 4, 6).

注意：

m 和 n 的范围在 [1, 30000] 之间。
k 的范围在 [1, m * n] 之间。

解法1: 二分查找 (O(n*n)超时)

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        # 1. 先生成 乘法表，O(n*n) 超时
        # 乘法表 有个特性： mxn 为乘法表中的 最大值，乘法表取值范围[1, m*n]， 同时 共有 m*n个数
        # 在 [1, m*n] 使用二分查找， mid为 中值， 求的 小于mid的值个数为x，若 x <k,则第k小数 在 （mid, m*n]之间，否则在 [0, mid]之间；
        def search(m, n, mid):
            count = 0
            # 遍历每一行 共 m行
            for i in range(1, m+1):  # 得到每行中 小于等于mid的 数字个数；
                count += min(mid//i, n)  
            return count

        left = 1
        right = m*n
        while left < right: # 为什么不带等号呢？
            mid = (left + right) // 2
            if search(m, n, mid) < k:  # 怎么求解 小于mid的数有多少呢？
                left = mid + 1
            else:
                right = mid # 有等于k的情况所以不 -1
        return left

本文地址：https://blog.csdn.net/qq_23944915/article/details/110880770

黄山市民网：https://www.huangshanshimin.com/

相关文章