704. Binary Search

Leetcode link

解题思路

题目要求我们从一个升序数组中找出一个特定的数，这种情况下二分法肯定是不二之选了，所以接下来的问题是怎么构造呢？

首先我们需要三个点：left, right, mid

left 用来确定二分范围的左边界

right 用来确定二分范围的右边界

mid 是本次二分范围的中心，用来确定下一次二分的区域

每次循环我们用 nums[mid] 的值做判断，如果 target 比较大，那么表示它如果存在必定在右边的区域，反之则一定在左边的区域

我们只需要通过调整二分的范围，然后重复上述步骤就可以不断缩小范围了，最后如果 left 超过了 right 则表示不存在这个数，直接返回 -1 就好

C++

class Solution {
 public:
  int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
      int mid = (left + right) / 2;
      // 如果恰巧落在 target 上，那就直接返回当前下标
      if (nums[mid] == target) return mid;
      // 如果 target 比当前的数大，那我们可以将范围移到右边区域
      if (target > nums[mid])
        left = mid + 1;
      // 如果 target 比当前的数小，那我们可以将范围移到左边区域
      else if (target < nums[mid])
        right = mid - 1;
    }
    return -1;
  }
};

Javascript

var search = function(nums, target) {
    let left = 0,
        right = nums.length-1;
    while(left <= right) {
        let mid = Math.floor((left + right) /2);
        if(nums[mid] === target) return mid;
        if(target < nums[mid])
            right = mid - 1;
        else if(target > nums[mid])
            left = mid + 1;
    }
    return -1;
};