代码随想录算法训练营Day0| LeetCode704: 二分查找

LeetCode 704 二分查找

先看了一下数组理论基础：数组基础
题目链接：704.二分查找

啥也没看，凭感觉直接上手：

class Solution(object):
	def search(self, nums, target):
		for num in nums:
			if num == target:
				return nums.index(num)
				break
		return -1

通过倒是通过了，但是，我写的什么东西？二分在哪里呢？

然后去看算法公开课了：
代码随想录：手把手带你撕出正确的二分法

看完重新写：

class Solution(object):
	def search(self, nums, target):
		left = 0
		right = len(nums) - 1
		# target 在左闭右闭区间内
		while left <= right:
			middle = (left + right) / 2
			if nums[middle] < target:
				left = middle + 1
			elif nums[middle] > target:
				right = middle - 1
			else:
				return middle
		return -1
'''
刚开始写的时候，因为题中说n在[1, 10000], 
直接right = 10000了，然后报错list index out of range,
自己找到bug咯~ 撒花！

再看了一下力扣官方题解，可改进的地方：
1.开头对left, right的赋值可以精简到一行：
left, right = 0, len(nums) - 1
2.求middle时使用整数除法：
middle = (left + right) // 2
'''

补充左闭右开写法:

# 补充左闭右开写法：
class Solution(object):
	def search(self, nums, target):
		left = 0
		right = len(nums) - 1
		# target 在左闭右开区间内
		while left < right:  # 区分点1:确保区间合法
			middle = (left + right) // 2
			if nums[middle] < target:
				left = middle + 1
			elif nums[middle] > target:
				right = middle
				# 区分点2:避免重复比较nums[middle]点
			else:
				return middle
		return -1

代码随想录的讲解：文章讲解

整理：

使用二分法的前提条件：
1.数组为有序（升序）数组；
2.数组中无重复元素
二分法注意事项：
1.想清楚区间的定义（不变量），保证区间合法；
2.if条件语句中避免重复比较

学习+做题+整理用时：2h
30/07/2024