[数组] 二分查找

简介

二分查找(Binary Search)算法，也叫折半查找算法，应用场景比较有限，其针对有序且无重复元素数组，查找某一特定元素查找思想有点类似分治思想，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0，其时间复杂度为O(logn)。

难点

• 循环条件的选择 left<=right || left<right
• 区间边界的更新方法 left right = middle 或 middle +/- 1

二者都与搜索区间的定义有直接关系，搜索区间是一个不变量，在查找过程中定义不能出现歧义，符合循环不变量规则：在while寻找中每一次边界的处理都要坚持根据区间的定义来操作。

算法实现

根据主流二分查找方法搜索区间的定义，可分为两种：[ , ] 左闭右闭 [ , ) 左闭右开

[ , ) 左闭右开

• 在极端情况下，如搜索区间为[1,1)时，意为左端点能取1值而右端点不能取1值，产生了明显逻辑冲突，所以left == right在区间[left, right)是没有意义的，循环条件选择left < right。
• 更新边界时，由于右端点为开区间，取值不能为右端点值，righ = middle即可，left = middle + 1。
• middle的取值，考虑到数值溢出风险，采用left + (right - left) / 2的计算方式。

public int Search(int[] nums, int target)
{
	int left = nums[0], right = nums.Length;
	while(left < right)
	{
	  	int middle = left + (right - left) / 2；
		if(nums[middle] > target) 
		  	right = middle;
	  	else if(nums[middle] < target) 
		  	left = middle + 1;
	  	else 
		  	return nums[middle];
	}
  	return -1;
}

[ , ] 左闭右闭

• 如搜索区间为[1,1]时，意为区间内仅有一个元素1，所以left == right在区间[left, right]是有意义的，循环条件选择left <= right。
• 由于右端点为闭区间，所以当前nums[middle]一定不是target，接下来查找的右区间结束下标位置right就是 middle - 1
• 其余和上述一致

public int Search(int[] nums, int target)
{
	int left = nums[0], right = nums.Length - 1;
	while(left <= right)
	{
	  	int middle = left + (right - left) / 2；
		if(nums[middle] > target) 
		  	right = middle - 1;
	  	else if(nums[middle] < target) 
		  	left = middle + 1;
	  	else 
		  	return nums[middle];
	}
  	return -1;
}

参考

文章内容参考ParKS和代码随想录编写，仅用于个人学习记录，若有疏漏，请指出。