思路
二分法的前提是数组有序。另外，当数组中存在重复元素时，最后返回的下标可能不唯一，具体实现不同，可能导致最后结果也不同。
left和right代表搜索区域的上下界，其基本思路就是把数组搜索区域分成两个区域，通过middle指针判别目标值属于哪个区域，然后在目标值所在的区域进一步二分，逐渐缩小范围并最后找到。
复杂度
- 时间复杂度：o(logn)
- 空间复杂度：o(n)（原地修改，所以空间消耗就是数组本身以及三个指针）
具体代码实现
代码实现难点主要在于：
- 循环的跳出条件到底是 left<right 还是 left<=right ；
- 当目标值比 middle 所指的值小时，表示在 middle 左边的区域，此时 right 到底时 middle 还是 middle-1
- 当目标值比 middle 所指的值大时，表示在 middle 右边的区域，此时 left 到底时 middle 还是 middle+1
一般在网上或者课本里所说的实现方法有两种，分别是左闭右闭（[left, right]）和左闭右开（[left, right))，这里我主要介绍第一种左闭右闭的实现，因为当你理解第一种的实现后，第二种就很简单啦。
左闭右闭是指left和right所指向的值也属于搜索区域内，于是此时循环的跳出条件应是left<=right，因为left=right是有意义的，表示此时的搜索区域就是当前两个指针所指的那个值。同理左闭右开跳出循环的条件应是left<right，因为当left=right时，搜索区间的上界是right的前一个值，故此时实际的搜索区间是没有意义的。
另外，左闭右闭时，当目标值比 middle 所指的值小时，right=middle-1，因为right所指的值时搜索区间的上界；同理，当目标值比 middle 所指的值大时，left=middle+1。
于是真个代码实现思路如下：
int search(vector<int>& nums, int target)
{
int left = 0;
int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
while (left <= right) // 当left==right，区间[left, right]依然有效，所以用 <=
{
int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
if (nums[middle] > target)
{
right = middle - 1; // target 在左区间，所以[left, middle - 1]
}
else if (nums[middle] < target)
{
left = middle + 1; // target 在右区间，所以[middle + 1, right]
}
else // nums[middle] == target
{
return middle; // 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}
相关leetcode题
34.在排序数组中查找元素的第一个和最后一个位置
35.搜索插入位置
704.二分查找