题目链接
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
其实二分查找的思想比较容易理解，但是问题就在于搜索区间的开闭。如果不能明白每次搜索区间的首尾的开闭情况就会出现不能正确查询出结果的问题。下面两个解法都能通过。
// 解法一
class Solution {
public:
int search(vector<int>& nums, int target) {
int begin = 0, end = nums.size() ;
while( begin < end ){
int middle = (begin + end ) / 2;
// 奇偶之分，导致中间位置有偏差
if(nums[middle] == target){
return middle;
}else if( nums[middle] > target){
end = middle;
}else{
begin = middle + 1;
}
}
return -1;
}
};
// 解法二
class Solution {
public:
int search(vector<int>& nums, int target) {
int left, right;
left = 0, right = nums.size() - 1;
while( left <= right ){
int mid = (left + right) / 2;
if( nums[mid] > target ) right = mid-1;
else if( nums[mid] < target) left = mid+1;
else
return mid;
}
return -1;
}
};
对于解法一：
我们将搜索区间定在了[ 0, nums.size() )， 显然我们在程序中是不能够访问 nums[ nums.size() ] 这个元素的，因为这样会导致边界溢出。在这个搜索区间下，我们的 middle = (left + right ) / 2 是正好指向整个搜索区间的中间元素的（元素个数为奇数个时正好指向中间位置，偶数个时则位于中间偏右位置）。
为了保持搜索区间的状态一致性，我们在后续进行二分的时候对应的区间也应当都是左开右闭的搜索状态，这里具体下来就是：对于第一次遍历的右顶点是属于越界情况，后续的搜索过程中，右顶点都是属于已遍历过无需再次遍历的状态。所以每次的二分区间为 [left, middle), [middle +1, right)。
假设当搜索区间中不存在目标元素时，搜索区间不断向两端收缩，最终到达 left == left或者 right == right 此时的搜索区间都是[left, left), [right, right) 的 状态，实际上这样的搜索区间都是空的，不可搜索的区间，因此这作为程序的终止条件。
同理对于解法二：
这个解法是将整个搜索区间定在了[0, nums.size() -1], 这样一来我们需要对整个搜索区间进行遍历，在这个搜索区间下，我们的 middle = (left + right ) / 2 是正好指向整个搜索区间的中间元素的（元素个数为奇数个时正好指向中间位置，偶数个时则位于中间偏左位置）
同上思路，我们进行二分划分搜索区间时，两边的顶点都应该时保持左开右开的状态，即[left, middle-1], [middle+1, right ]。
同样，在这个区间下最终的两端状态会变成[left, left],[right, right], 因为是都是开区间，所以这样的区间还有一个元素需要遍历，因此我们程序的结束条件为 left > right 。
综上， 在使用二分搜索进行查找元素时一定要保持最初的搜索空间和对应的子搜索空间是保持一致的搜索状态，这样才能正确对元素进行遍历检索。
