欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

二分查找方法 leetcode题

程序员文章站 2022-06-26 17:14:38
这里用来 记录 使用二分查找方法 的题目1.面试题 10.03. 搜索旋转数组搜索旋转数组。给定一个排序后的数组,包含n个整数,但这个数组已被旋转过很多次了,次数不详。请编写代码找出数组中的某个元素,假设数组元素原先是按升序排列的。若有多个相同元素,返回索引值最小的一个。示例1: 输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5 输出: 8(元素5在该数组中的索引)示例2: 输入:arr = ....

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

1. 704. 二分查找

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

示例 1:

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

提示:

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. 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 (没有找到)

提示:

  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).

注意:

  1. m 和 n 的范围在 [1, 30000] 之间。
  2. 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