二分搜索Python（一、寻找一个数 二、寻找左侧边界的二分搜索 三、寻找右侧边界的二分搜索 四、力扣34.在排序数组中查找元素的第一个和最后一个位置 5、求sqrt 6、寻找峰值 7、旋转数组）_力扣寻找左侧边界的二分查找

二分搜索也叫做二分查找，需要用while循环实现
针对指针i,j，我们可以得出其中间值为 mid=i+(j-i)//2
不考虑mid=(i+j)//2的写法的原因是，防止i,j两个指针过大，相加值会溢出的问题
一、Leetcode704 二分查找 题目链接

class Solution:
	def search(self, nums:List[int], target:int):
		i,j = 0, len(nums)-1 # 设定左右指针
		while i<=j: # 必须考虑i = j的情况，终止条件为i=j+1
			mid = i+(j-i)//2 # python // 表示除数向下取整
			# mid还可以写成mid = (i+j)//2 结果是相同的，但是这种情况会产生两个数过大，相加溢出的情况，所以建议写成mid = i+(j-i)//2的形式
			if nums[mid] < target: # 如果中间值小于目标值时
				i = mid+1 # 将搜索区间变为[mid+1,j]
			elif nums[mid]> target: # 如果中间值大于目标值时
				j = mid-1
			else:
				return mid
		return -1
1
2
3
4
5
6
7
8
9
10
11
12
13

二、寻找左侧边界的二分搜索

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，target若出现会重复出现多次，写一个函数搜索 nums 中的target的左侧边界值，如果目标值存在返回下标，否则返回 -1。

def findLeft(nums,target):
	if not nums or target not in nums:
		return -1
	i,j = 0, len(nums)-1
	while i<=j:
		mid = i+(j-i)//2
		if nums[mid] >= target:
			j = mid-1
		else:
			i = mid+1
	return i # 返回左侧边界索引
		
1
2
3
4
5
6
7
8
9
10
11
12

三、寻找右侧边界的二分搜索

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，target若出现会重复出现多次，写一个函数搜索 nums 中的target的右侧边界值，如果目标值存在返回下标，否则返回 -1。

def findRight(nums,target):
	if not nums or target not in nums:
		return -1
	i,j = 0, len(nums)-1
	while i<=j:
		mid = i+(j-i)//2
		if nums[mid] <= target:
			i = mid+1
		else:  # nums[mid] > target
			j = mid-1
	return j # 返回右侧边界索引
1
2
3
4
5
6
7
8
9
10
11

四、Leetcode34.在排序数组中查找元素的第一个和最后一个位置 题目链接

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
    	if not nums or target not in nums:
    		return [-1,-1]
    	res = []
	    i,j = 0, len(nums)-1
    	# 求左侧边界索引
    	while i<=j:
    		mid = i + (j-i)//2
    		if nums[mid]>=target:
    			j = mid-1
    		else: 
    			i = mid+1
    	res.append(i)
    	# 求右侧边界索引
    	i, j = 0, len(nums)-1
    	while i<=j:
    		mid = i + (j-i)//2
    		if nums[mid] <= target:
    			i = mid+1
    		else: 
    			j = mid-1
    	res.append(j)
    	return res 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

还有一种一行解决的方法，但是面试的时候，这么写多半会被面试官鄙视

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
    	if target in nums:
    		return [nums.index(target), nums.index(target)+ nums.count(target)-1]
    	else:
    		return [-1,-1]
1
2
3
4
5
6

五、Leetcode69.Sqrt 题目链接

方法一：

class Solution:
    def mySqrt(self, x: int) -> int:
    	# 数学公式推导方法，面试的时候用这种方法应该会被面试官鄙视
    	# sqrt(x) = x^1/2 = e^(1/2*lnx)
    	if x==0:
    		return 0
    	ans = int(math.exp(0.5*math.log(x)))
 	    # 这种方法需要注意的是，由于计算机无法存储浮点数的精确值，而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程会存在误差，
        # 例如x = 2147395600时，e^(1/2*lnx)的计算结果与正确值43640相差10^-11，这样在对结果取整数部分时，会得到46339这个错误结果，
        # 因此在都得到结果的整数部分ans后，我们应该找出ans与ans+1哪个是真正的答案
    	return ans+1 if (ans+1)**2 < x else ans
1
2
3
4
5
6
7
8
9
10
11

方法二：二分查找

class Solution:
    def mySqrt(self, x: int) -> int:
    	i,j,ans = 0,len(nums)-1, -1
    	while i<=j:
    		mid = i+(j-i)//2 # 求中间值
			if mid*mid<=target:
				i = mid+1
				ans = mid # 虽然比target小，但是不断逼近
			elif mid*mid > target: # 已经比target大了，应该缩小j的值，从而让中间值变小
				j = mid-1
		return ans
1
2
3
4
5
6
7
8
9
10
11

方法二：牛顿迭代法（设目标值为C，则构造函数 y=x^2-C）

class Solution:
    def mySqrt(self, x: int) -> int:
        # 牛顿迭代法(机器学习方法面试应该比较喜欢这种解法)
        # 时间复杂度 O(logx), O(1)
        # 设给定的非负整数为C，此时求解C的平方根的式子为：y = x^2-C
        # 牛顿迭代法的本质是借助泰勒级数，从初始值(此时设定初始值x0=C)，在每一步的迭代中，我们找到函数图像上的点(xi,f(xi)),过该点做一条斜率为该导数f'(xi)的直线
        # 与横轴的交点记为xi+1,xi+1相较于xi而言距离零点更近。经过多轮迭代后，就可以得到一个距离为0的非常近的交点。
        # 经过推导可得迭代公式为 xi+1 = 1/2(xi+C/xi)
        if x == 0:
            return 0
        C ,x0 = float(x), float(x)
        while True:
            xi = 0.5*(x0+C/x0)
            if abs(x0-xi) <1e-7:
                break
            x0 = xi
        return int(x0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

6、Leetcode162 寻找峰值 题目链接

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
    	n = len(nums)-1
    	i, j = 0, n
    	while i<=j:
    		mid = i+(j-i)//2
    		if mid-1 >=0 and mid+1 <= n and nums[mid]> nums[mid-1] and nums[mid]>nums[mid+1]: # 如果mid的前后索引值都在nums里，并且都nums[mid]值大于两侧的
    			return mid
    		if mid+1 <= n and nums[mid] < nums[mid+1] : # and前后是有逻辑顺序的
    			i = mid+1
    		else:
    			j = mid-1
    	return mid
    			 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

7.1 Leetcode33 搜索旋转排序数组 题目链接

class Solution:
    def search(self, nums: List[int], target: int) -> int:
    	i,j = 0, len(nums)-1
    	while i<=j:
    		# 照比常规的二分查找只要加一个判断条件就可以了
    		mid = i+(j-i)//2
    		if nums[mid] == target:
    			return mid
    		elif nums[mid] > target: # 中间值大于目标值：
    			if nums[i]<=nums[mid] and target< nums[i]: # 如果mid左边有序且target不在左边，向右查找
    				i = mid+1
    			else:# 其余情况向左查找
    				j = mid-1
    		else: # 如果目标值大于中间值
    			if nums[j]>=nums[mid] and target>nums[j]:#如果mid右边有序，且target不在右边，则向左查找
    				j = mid-1
    			else:
    				i = mid+1
    	return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

7.2 Leetcode153 寻找旋转排序数组中的最小值 题目链接

class Solution:
    def findMin(self, nums: List[int]) -> int:
    	# 主要思想是用nums[mid]与nums[high]比较
    	# 如果nums[mid]>nums[high],代表最小值在mid的右侧
    	# 如果nums[mid]<nums[high], 代表最小值在mid的左侧
    	i,j = 0, len(nums)-1
    	while i<j:
    		mid = i+(j-i)//2
    		if nums[mid]>nums[j] # 都是跟右指针比
    			# 如果中间值比右指针大，则说明最小值在mid右侧，可以让mid+1，这样也不会错过最小值
    			i = mid+1
    		else: # nums[mid]<=nums[j] # 中间值比右指针小，说明最小值在右指针左侧
    			j = mid
    	return nums[j]    	
1
2
3
4
5
6
7
8
9
10
11
12
13
14