算法入门.md

第一天

704.二分查找

给定一个升序数组 nums，一个目标值 target，要求找到 nums 中等于 target 的值，返回值的索引，否则就返回-1。

一开始我没有想到二分查找，毕竟我也不会这个…直观感受是，用 for 循环遍历就可:

var search = function (nums, target) {
  for (let i = 0; i < nums.lenght; i++) {
    if (nums[i] === target) return i
  }

  return -1
}

或者可以直接使用 js 中的findIndex方法:

var search = function (nums, target) {
  return nums.findIndex((item) => item === target)
}

虽然说上面的两种方法都可以很快得到想要的答案，但是毕竟题目为二分查找，还是得按照题目来，对吧…

于是我看了一下官方题解和大神写的文章。

二分查找，简而言之就是将数据分成左右两份，并且找出一个中间索引。若是中间索引的值大于目标值，说明目标值在左侧；小于目标值，那么就在右侧。每次查找时，都会重新将数据对半分，并重新找中间索引，如果中间索引的值等于目标值，直接返回，否则就重复前面的步骤。

var search = function (nums, target) {
  let left = 0,
    right = nums.length - 1

  while (left <= right) {
    let middle = left + Math.floor((right - left) / 2)
    if (nums[middle] > target) {
      right = middle - 1
    } else if (nums[middle] < target) {
      left = middle + 1
    } else {
      return middle
    }
  }

  return -1
}

var search = function (nums, target) {
  let left = 0,
    right = nums.length

  while (left < right) {
    let middle = left + Math.floor((right - left) / 2)
    if (nums[middle] > target) {
      right = middle
    } else if (nums[middle] < target) {
      left = middle + 1
    } else {
      return middle
    }
  }

  return -1
}