这里用来 记录 使用二分查找方法 的题目
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. 搜索旋转数组
33. 搜索旋转排序数组
搜索旋转数组。给定一个排序后的数组，包含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
5.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
