二分法的理解

使用循环实现

先看一道leetcode上的题：
在排序数组中查找元素的第一个和最后一个位置

题目明确要求 实现的时间复杂度为 O(log n)。这个要求，很容易让我们联想到二分法这个算法。
再拆解下题目描述，已经是有序数组，满足二分查找的前提，那么只需要通过二分法找到目标元素的位置，再向前后迭代获取最左和最右的索引即是题目所需要的答案。

列一下所实现的二分查找的代码：

//只返回查找到的位置，不确定是最左或最右
int BinarySearch(vector<int>& nums, int target)
{
	assert(nums.size() >= 2);
	int left = 0;
	int right = nums.size() - 1;
	while (left <= right)
	{
		int mid = (right + left) / 2;
		int midval = nums[mid];
		if (midval < target) //往右折
		{
			left = mid + 1;	//由于left <= mid ，所以要确保left右移需要加1
		}
		else if (midval > target) //往左折
		{
			right = mid - 1;	//由于mid<right, 必会使right左移，但这里mid已经检查过一遍，最差情况会导致再检查一次，
		}
		else
		{
			return mid;
		}
	}
	return -1;
}

代码理解:

• 二分查找需要确定区间，每次折半，所以需要定义左右端点位置 left、right
• 在循环内逐步缩小区间，结束区间的条件定为 left<=right，意为在left==right还要进行一次判断，该值是不是target目标值
• 折半查找，需要定义mid位置，mid = (right+left)/2，这样做的话，在left<right时，必然会有mid<right，mid>=left条件的成立
• 将mid位置的值与target进行比较，三种情况分别处理。
  • 相等则返回，表示已查找到
  • 中值小于target值，表示target值在右区间，需要将left端点右移，left = mid+1，需要加1，这样的最极端情况是left==right，循环后再判断一次即可
  • 中值大于target值，表示target值在左区间，需要将right端点左移，right = mid-1，减1，这样的最极端情况是left==mid的时候，这种情况的时候表示无法左移了，那么right==mid-1==left-1，会退出循环，也是不存在遗漏查找的情况
  • 默认返回-1，表示查找不到；如果查找到，会直接在循环中就返回

值得注意的是，如果代码如上，那么mid = (right+left)/2 和 mid = (right+left+1)/2 两种情况的处理没有区别。

使用递归实现

依然通过leetcode上一个题来举例：
搜索旋转排序数组 II
旋转后的数组是没法保证折半之后左右区间都是肯定满足左区间的数小于等于右区间的数的
忽略一些细节的判断，我们可以简单的在折半之后两边都进行查找，这样的话，使用递归方法来实现会使代码简单直观很多。

int BinarySearch(vector<int>& nums, int target, int left, int right)
{
	if (left > right)
	{
		return -1;
	}
	int mid = (left + right) / 2;
	int midval = nums[mid];
	if (midval == target)
	{
		return mid;
    }
	
	int result = BinarySearch(nums, target, mid + 1, right);
	if (result != -1)
	{
		return result;
	}
	return BinarySearch(nums, target, left, mid - 1);
}

然后简但调用就可以达到查找的目的

bool search(vector<int>& nums, int target) {
    return BinarySearch(nums, target, 0, nums.size() - 1) != -1;
}

二分折半的思想是共通的，注意临界点的情况即可。