704. 二分查找

我写的第一个题目！

原版二分查找题目，从这个题目了解二分查找。

基本思想：把整个有序数组从中间切开。看中间这个元素和我要找的东西之间的关系，如果要找的比这个东西还大，按照升序的原则，那要找的应该在右边，我应该去右边那个块找；如果要找的比这个东西还小，按照升序的原则，要找的在左边，去左边这个块找；如果就是这个，那不就好了吗，找到了啊，退出。

怎么界定目前找的是哪一个”块“？用区间的概念。左闭右闭的区间，用left和right存储，作为左右边界。中间的位置，直接左右边界加起来除以2.

怎么做到所谓的”去左边/右边的块“？那就调整区间的边界呗，你这个middle把正在查找的块分成了，middle本身和左右两个区域，去左边就让右边界缩回到middle左边，去右边就让左边界缩回到middle右边。

while (left <= right)这个条件，因为左边界等于右边界代表这个闭区间还是存在的，只不过只有一个元素了，但终究是没被搜索过，还需要继续进行。

class Solution {
  public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, middle;
        while (left <= right) {
            middle = (left + right) / 2;
            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] < target) {
                left = left + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
};