1.简介

二分法查找是一种常用的数据查找方法，它的前置要求是：

用于查找的内容在逻辑上要求是有序的
查找的数量仅限于一个

比如在一个有序的数组并且无重复元素的数组中，例如[1, 2, 3, 4, 5, 6]，需要查找3的位置就可以使用二分查找

目前来说，二分法查找主要有两种方法：

左闭右闭 [left, right]
左闭右开 [left, right)

就个人来说，更推荐左闭右闭写法，更符合程序员对于数组的使用习惯

2.栗子

题目如下：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例一：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例二：

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

出自704. 二分查找 - 力扣（LeetCode） (leetcode-cn.com)

二分法的思想很简单，因为整个数组是有序的，可以取中间值middle：

若target小于middle时，便舍弃middle右侧的部分
若target大于middle时，便舍弃middle左侧的部分
若target等于middle，middle便是你所寻找的target

有些人可能会纠结middle的取值，即数组长度取偶数或奇数时的middle值

其实这没必要去担心，当长度为奇数时：

array长度为5，middle = (right - left) = 2，虽然前后部分长度差1，但是对后续求解并没有影响

长度为偶数时：

array长度为6， middle = (right - left) = 3，正好是中间的数字

3.左闭右闭算法

先上代码

int search(int* nums, int numsSize, int target){
    int left = 0;
    int right = numsSize-1;
    while(left<=right){
        int middle = left + ((right-left)/2);
        if(nums[middle]<target)
            left = middle+1;
        else if(nums[middle]>target)
            right = middle-1;
        else
            return middle;
    }
    return -1;
}

解释：

先设置left和right，左闭右闭时为数组的两端，一个为最左端，一个为最右端

接下来进入循环，先取得第一次middle值

1	int middle = left + ((right-left)/2);

因为left=0，这段代码含义其实等价于(right - left)

接下来判断target与middle的关系

当middle<target时，这就意味着中值在目标左侧，这时将左值移动到中值的左1位（因为中值已经小于目标，没必要再一次比较）
当middle>target时，这就意味着中值在目标右侧，这时将右值移动到中值的右1位（因为中值已经大于目标，没必要再一次比较）

当进行n次循环后，中值最后等于目标，这时候返回中值，即要求的目标值

4.左闭右开算法

先上代码：

int search(int* nums, int numsSize, int target)
{
	int left = 0;
	int right = numsSize;
	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 middle;
	}
	return -1;
}