LeetCode-二分查找
LeetCode-二分查找
二分查找
二分查找也称为折半查找，每次都能将查找区间减半，这种折半特性的算法时间复杂度为 O(logN)。
中值计算
有两种计算中值 m 的方式：
- m = (l + h) // 2
- m = l + (h - l) // 2
l + h 可能出现加法溢出，也就是说加法的结果大于整型能够表示的范围。但是 l 和 h 都为正数，因此 h - l 不会出现加法溢出问题。所以，最好使用第二种计算法方法。
69. x 的平方根
实现 int(math.sqrt(x)) 函数。
示例：
输入: 4
输出: 2
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。解法：
不断缩小区间，在将该区间中位数与x做比较
以30为例，区间缩小为[0,16] -> [0,7] -> [4,7] -> [4,5] -> [5,5]
class Solution:
def mySqrt(self, x: int) -> int:
# 为了照顾到 0 把左边界设置为 0
left = 0
# 为了照顾到 1 把右边界设置为 x // 2 + 1
right = x // 2 + 1
while left < right:
# 注意：这里一定取右中位数，如果取左中位数，代码可能会进入死循环
# mid = left + (right - left + 1) // 2
mid = (left + right + 1) >> 1
square = mid * mid
if square > x:
right = mid - 1
else:
left = mid
# 因为一定存在，因此无需后处理
return left744. 寻找比目标字母大的最小字母
给定一个有序的字符数组 letters 和一个字符 target，要求找出 letters 中大于 target 的最小字符，如果找不到就返回第 1 个字符。
示例:
输入:
letters = ["c", "f", "j"]
target = "a"
输出: "c"
输入:
letters = ["c", "f", "j"]
target = "c"
输出: "f"
输入:
letters = ["c", "f", "j"]
target = "k"
输出: "c"解法：
二分法
class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
l, h = 0, len(letters) - 1
while l < h:
m = (l + h) // 2
if letters[m] > target:
h = m
else:
l = m + 1
return letters[l] if letters[l] > target else letters[0]没二分法：
class Solution:
def nextGreatestLetter(self, letters: [str], target: str) -> str:
for i, j in enumerate(letters):
if target < j:
return j
else:
return letters[0]540. 有序数组中的单一元素
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例：
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
输入: [3,3,7,7,10,11,11]
输出: 10解法：
令 index 为 Single Element 在数组中的位置。在 index 之后，数组中原来存在的成对状态被改变。如果 m 为偶数，并且 m + 1 < index，那么 nums[m] == nums[m + 1]；m + 1 >= index，那么 nums[m] != nums[m + 1]。
从上面的规律可以知道，如果 nums[m] == nums[m + 1]，那么 index 所在的数组位置为 [m + 2, h]，此时令 l = m + 2；如果 nums[m] != nums[m + 1]，那么 index 所在的数组位置为 [l, m]，此时令 h = m。
class Solution:
def singleNonDuplicate(self, nums: [int]) -> int:
l = 0
h = len(nums) - 1
while l < h:
m = l + (h - l) // 2
if m % 2 == 1:
m -= 1
if nums[m] == nums[m + 1]:
l = m + 2
else:
h = m
return nums[l]278. 第一个错误的版本
题目描述：给定一个元素 n 代表有 [1, 2, …, n] 版本，在第 x 位置开始出现错误版本，导致后面的版本都错误。可以调用 isBadVersion(int x) 知道某个版本是否错误，要求找到第一个错误的版本。
示例：
给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本解法：
如果第 m 个版本出错，则表示第一个错误的版本在 [l, m] 之间，令 h = m；
否则第一个错误的版本在 [m + 1, h] 之间，令 l = m + 1。
class Solution:
def firstBadVersion(self, n):
l = 1
h = n
while l<h:
m = l + (h-l) // 2
if isBadVersion(m):
h = m
else:
l = m + 1
return l153. 寻找旋转排序数组中的最小值
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。