二分法类似于双指针，不过二分的方法主要用于排序数组中元素的查找。
704. 二分查找
给定一个 n 个元素有序的（升序）整型数组nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
- 二分查找法
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
# 二分思路
mid = left + (right - left)//2
# 目标值在右侧
if nums[mid] < target:
left = mid + 1
# 目标值在左侧
elif nums[mid] > target:
right = mid - 1
# 恰好是目标值
else:
return mid
return -1
- 方法2：二分查找法的第二种形式
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
# 直接排除一个区间
while left < right:
mid = left + (right - left)//2
# 排除左侧区间
if nums[mid] < target:
left = mid + 1
# 排除右侧区间
else:
right = mid
# 直接剩下left=right单一区间，判断是否相等
if nums[left] == target:
return left
else:
return-1
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
输入: nums = [1,3,5,6], target = 5
输出: 2
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left)//2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
# 只能返回左侧边界的数
return left
69. Sqrt(x)
给你一个非负整数 x ，计算并返回 x 的 算术平方根
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
class Solution:
def mySqrt(self, x: int) -> int:
left = 0
right = x
result = -1
while left <= right:
# 二分法为了减少时间复杂度
mid = left + (right - left)//2
# 因为结果只保留整数部分，因此求解目标是：找到 k^2 <= x 的最大结果
if mid*mid <= x:
result = mid
left = mid + 1
else:
right = mid - 1
return result
50. Pow(x, n)
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。
- 方法1：使用内置函数
class Solution:
def myPow(self, x: float, n: int) -> float:
return pow(x,n)
- 方法2：递归+分治
x→x^2 →x^4 →x^8 →x^16 →x^32 →x^64
x→x^2 →x^4 →x^9 →x^19 →x^38 →x^77
从右向左分析，可以得知递归的思路
class Solution:
def myPow(self, x: float, n: int) -> float:
def quickMul(N):
# 二分的思路
if N == 0:
return 1.0
y = quickMul(N // 2)
# 判断是否除尽
if N % 2 == 0:
return y*y
else:
return y*y*x
# 对正负进行分类判断
if n >= 0:
return quickMul(n)
else:
return 1.0 / quickMul(-n)
287. 寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。
输入：nums = [1,3,4,2,2]
输出：2
- 使用二分法在排序数组中进行查找多余的数字
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
left = 0
right = len(nums) - 1 # 因为重复了一个数字，所以右区间少一个元素
while left < right:
mid = left + (right - left)//2
count = 0
for num in nums:
# 统计小于等于mid值的数的个数
if num <= mid:
count += 1
# 当统计得到的数小于等于中间数，则意味着在mid的右侧查找
if count <= mid:
left = mid + 1
else:
right = mid
return left
367. 有效的完全平方数
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
输入：num = 16
输出：true
- 使用二分法查找答案
class Solution:
def isPerfectSquare(self, num: int) -> bool:
left = 0
right = num
while left < right:
mid = left + (right - left)//2
if mid*mid < num:
left = mid + 1
elif mid*mid > num:
right = mid - 1
else:
left = mid
break
return left*left == num
167. 两数之和 II - 输入有序数组
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
- 双指针，对于一个非递减序列，从两端向中间查找
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left = 0
right = len(numbers) - 1
# 注意left不能等于right,不可以使用相同的元素
while left < right:
if numbers[left] + numbers[right] == target:
return [left+1, right+1]
elif numbers[left] + numbers[right] < target:
left += 1
else:
right -= 1
33. 搜索旋转排序数组
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4(下标)
# 遍历查找
class Solution:
def search(self, nums: List[int], target: int) -> int:
for i in range(len(nums)):
if nums[i] == target:
return i
return -1
# 二分法
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left)//2
if nums[mid] == target:
return mid
# 1 先将旋转数组看作是左右两个递增的数组
# 首先需要判断mid索引位置的数在左右哪一个数组
# 再判断target在左右那个数组
if nums[mid] >= nums[left]:
# mid属于左边数组
if nums[mid] > target and nums[left] <= target:
# target在左边数组
right = mid - 1
else:
# target在右边数组
left = mid + 1
elif nums[mid] :
# mid在右侧数组
if nums[mid] < target and nums[right] >= target:
# target在右边数组
left = mid + 1
else:
# target在右边数组
right = mid - 1
return -1
81. 搜索旋转排序数组 II
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
# 方法1：直接判断目标值是否在数组中，等同于遍历查找
class Solution:
def search(self, nums: List[int], target: int) -> bool:
return target in nums
# 方法2：二分法 利用原来数组的有序性
class Solution:
def search(self, nums: List[int], target: int) -> bool:
n = len(nums)
if n == 0:
return False
left = 0
right = len(nums) - 1
while left < right:
mid = left + (right - left)//2
# 1 mid在左边的数组
if nums[mid] > nums[left]:
# target在左边的数组
if nums[mid] >= target and nums[left] <= target:
right = mid
else:
left = mid + 1
# 2 mid在右边的数组
elif nums[mid] < nums[left]:
# target在右边的数组
if nums[mid] < target and nums[right] >= target:
left = mid + 1
else:
right = mid
else:
if nums[mid] == target:
return True
else:
left += 1
return nums[left] == target
