Day 18 : 二分搜寻 Binary Search

生活上我们可能有遇过一些二分搜寻的例子。
例如以前如果有当过助教的经验，有时候我们在收学生作业时会作业按照学号由小到大排好，
假设有100位学生001~100，我们要找第69号，我们可能会大概拆分成两叠在从後面那一叠，而非从头开始慢慢算，这就是二分搜寻的生活例子！

从这个例子中可以发现，如果我们今天要从已经排列好的东西找到想要的结果
→ 我们都可以想想二分搜寻是否可以派上用场！

那我们来看看这题题目吧！

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

今天拿nums = [-1,0,3,5,9,12] ，我们想要寻找9是否在nums内，如果有救回传他的index，没有则回传-1。
一开始我们要出中位数的index，我们先建立一个左指标和右指标分别指向nums的头和尾，计算中间值index。

(0+5)/2 无条件舍去法，得到2。
我们得到 nums[2] 为 3，又因 3 < 9 ，所以我们知道9的index一定是在2的右手边
於是我们就可以忽略 index 从 0 到 ２的元素！直接从 index=３开始寻找，所以我们把左指标移到了 nums[3]

一样找中间index
( 3 + 5 ) / 2 = 4
nums[4] = 9 於是我们找到了9的index为4

以上就是二分搜寻。

那如果我们要寻找的数不在阵列中会发生什麽事？
我们一样用同样得阵列来寻找 target = 10
我们接着nums[4] = 9，所以10的index一定会在4的右手边。
我们要把左指标移到index为5的位置，这时候发现左边跟右边的指标指向同一个位置了！
但是 nums[5] = 12≠10 对吧？
又因为 10 < 12
这时候我们想要把右指标移动到 index 为 5 - 1 = 4
但这样却变成右边指标跑道左边指摽的左手边了！
这时我们就可以理所当然地停止搜寻，也就是这个数根本存在！
时间复杂度为 O(logN)
空间复杂度方面，则牵涉到我们的实作方式有关。

如果是用iteratively的方式，Space可以为O(1)，只需要纪录中间index
如果是recursively的方式，用到stack的资料结构，就会让Space变成O(logN)

让我们来看一下两种方式的实作吧！

// iteratively
var search = function (nums, target) {
  return binarySearchMethod(nums, target, 0, nums.length - 1);
};

const binarySearchMethod = (array, target, left, right) => {
  while (left <= right) {
    const midIndex = Math.floor((left + right) / 2);
    const midNumber = array[midIndex];
    if (target === midNumber) {
      return midIndex;
    } else if (target < midNumber) {
      right = midIndex - 1;
    } else {
      left = midIndex + 1;
    }
  }
  return -1;
};

//recursively

var search = function (nums, target) {
  return binarySearchMethod(nums, target, 0, nums.length - 1);
};
const binarySearchMethod = (array, target, left, right) => {
  if (right < left) return -1;
  const midIndex = Math.floor((left + right) / 2);
  const midNumber = array[midIndex];
  if (target === midNumber) {
    return midIndex;
  } else if (target < midNumber) {
    return binarySearchMethod(array, target, left, midIndex - 1);
  } else {
    return binarySearchMethod(array, target, midIndex + 1, right);
  }
};

明天题目预告： 二元树的三种走访 BST Traversal