二分查找的正确编写方法

发表于 2023-10-31 本文字数 903 字阅读时长 1 分钟

写二分法，区间的定义一般为两种，闭区间或者开区间

（1）左闭右闭区间 $[left, right]$

while(left<=right) 要使用 <= ，因为 left==right 是有意义的，所以使用 <=
if (nums[middle] > target) ， right 要赋值为 middle - 1 ，因为当前这个 nums[middle] 一定不是 target ，那么接下来要查找的左区间结束下标位置就是 middle - 1 ，反之同理。

	class Solution:
	def search(self, nums: List[int], target: int) -> int:
	left, right = 0, len(nums) - 1

	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

（2）左闭右开区间 $[left, right)$

while(left<right) 要使用 < ，因为 left==right 是没有意义的，所以使用 <
if (nums[middle] > target) ， right 要赋值为 middle ，因为当前 nums[middle] 不等于 target ，去左区间继续寻找，而寻找区间是左闭右开区间，所以 right 更新为 middle ，即：下一个查询区间不会去比较 nums[middle]

	class Solution:
	def search(self, nums: List[int], target: int) -> int:
	left,right =0, len(nums)
	while left < right:
	mid = (left + right) // 2
	if nums[mid] < target:
	left = mid+1
	elif nums[mid] > target:
	right = mid
	else:
	return mid
	return -1

leetcode 编程技巧