最常见的查找算法一个顺序查找，另一个是二分查找。
所谓顺序查找就是依次遍历，找到那个目标即可，顺序查找的话，这里就不赘述。一般数组查找方法通用的接口都是找到了返回下标，找不到则返回-1。
比如JS中indexOf方法，其实就是search。

binary search（二分查找）

二分查找是针对有序数组非常高效的查找算法，时间复杂度是O(logN)，非常牛逼了。
下面是二分查找的一个简单实现：

  1. function search(arr, target) {
  2.   let low = 0;
  3.   let high = arr.length - 1;
  5.   while (low <= high) {
  6.     let mid = Math.floor((low + high) / 2);
  8.     if (target < arr[mid]) {
  9.       high = mid - 1;
  10.     } else if(target > arr[mid]) {
  11.       low = mid + 1;
  12.     } else {
  13.       return mid;
  14.     }
  15.   }
  17.   return -1;
  18. }

LeetCode374:猜数字游戏

题目：
猜数字游戏的规则如下：
每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

这是一个典型的二分查找，只不过，这个判断结果是需要调用预置接口的。但总体来讲没啥技术含量。

LeetCode69:实现 int sqrt(int x) 函数

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。
这个题…. 竟然做了许久

  1. var mySqrt = function(x) {
  2.     // 二分查找
  3.     let left = 0;
  4.     let right = x;
  5.     let mid = 0;
  7.     let res = 0;
  8.     while(left <= right) {
  9.         mid = Math.floor((left + right) / 2);
  10.         if( mid * mid <= x) {
  11.             res = mid;
  12.             left = mid + 1
  13.         }  else {
  14.             right = mid - 1
  15.         }
  16.     }
  17.     return res
  18. };