二分查找方法 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
提示:
- 你可以假设
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
给定一个按照升序排列的整数数组 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]
搜索旋转数组。给定一个排序后的数组,包含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
几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第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
推荐阅读
-
Python基于二分查找实现求整数平方根的方法
-
C#使用二分查找法判断指定字符的方法
-
Java~利用二分查找完成牛客经典算法题--查找旋转数组的最小数字
-
python二分查找算法的递归实现方法
-
Python基于二分查找实现求整数平方根的方法
-
[Leetcode][第410题][JAVA][分割数组的最大值][动态规划][二分]
-
LeetCode的一道题引申的python实现的对字符串进行分词,提取词频的方法
-
JavaScript折半查找(二分查找)算法原理与实现方法示例
-
PAT_甲级_1050 String Subtraction (20分) (C++)【签到题/二分查找/字符串处理】
-
leetcode278. 第一个错误的版本(二分查找)