704. Binary Search

问题：

二分查找，给定一个已排序的数组，和一个目标值target

在该数组中找到target的index返回，若没找到，则返回-1。

Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Note:
You may assume that all elements in nums are unique.
n will be in the range [1, 10000].
The value of each element in nums will be in the range [-9999, 9999].

　　

解法：二分查找(Binary Search)

参考 69. Sqrt(x)  的解释部分。

代码参考：

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