题解 | #二分查找-I#

方法：二分法

题设是一个升序且无重复元素的数组，利用二分法能很容易的查找元素。

1、获取数组的中间元素，会有三种情况：

如果目标值等于中间元素即找到；

如果目标值小于中间元素，则目标值在左侧；

如果目标值大于中间元素，则目标值在右侧；

2、不断的缩小范围，直到最终只剩一个元素，若仍然没找到目标值则返回-1；否则返回下标。

时间复杂度：o(logⁿ)

空间复杂度：o(1)

class Solution {
  public:
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0)
            return -1;
        int left = 0;
        int right = nums.size() - 1;


        while (left <= right) {
            int mid = (left + right) / 2;

            if (target == nums[mid])
                return mid;
            else if (target < nums[mid])
                right = mid - 1;
            else if (target > nums[mid])
                left = mid + 1;
        }
        return -1;
    }
};