解析前端面试之二分查找算法

二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。

二分法查找的思路如下：

（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。

（2）如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。

（3）如果某一步数组为空，则表示找不到目标元素。

二分法查找的时间复杂度O(logn)。

先看一个解法

    function binarySearch(argTarget, argArry) {
      let count = 0;
      let startIndex = 0,
        endIndex = argArry.length - 1;
      while (startIndex < endIndex && count++ < 1600) {
        debugger;
        let middleIndex = ((startIndex + endIndex) / 2) | 0;
        let number = argArry[middleIndex];
        if (number === argTarget) {
          return middleIndex;
        } else if (number > argTarget) {
          endIndex = middleIndex;
        } else {
          startIndex = middleIndex;
        }
      }

      return -1;
    }

特意加了count变量防止陷入死循环
用 console.log(binarySearch(0, [0, 1, 2, 3])); 输出为0，直到2的时候都会成功，
接下来请打开Chrome开发者工具，用console.log(binarySearch(3, [0, 1, 2, 3]));做测试，多点几次startIndex一直在2，endIndex一直在3。
长按如下按钮，点击第二个会输出 -1 。

middleIndex 位置上没有匹配的话，显然不用继续参与运算了，所以应改为endIndex = middleIndex - 1;、startIndex = middleIndex + 1;
这次没有陷入死循环，startIndex是3，endIndex是3，再算一次就可以找到，循环条件要改为while (startIndex <= endIndex && count++ < 1600)。
改动之后

    function binarySearch(argTarget, argArry) {
      let count = 0;
      let startIndex = 0,
        endIndex = argArry.length - 1;
      while (startIndex <= endIndex && count++ < 1600) {
        debugger;
        let middleIndex = ((startIndex + endIndex) / 2) | 0;
        let number = argArry[middleIndex];
        if (number === argTarget) {
          return middleIndex;
        } else if (number > argTarget) {
          endIndex = middleIndex - 1;
        } else {
          startIndex = middleIndex + 1;
        }
      }

      return -1;
    }

当startIndex比endIndex小1时，((startIndex + endIndex) / 2) | 0导致middleIndex偏向小的数， 如果目标在endIndex上会出现问题，startIndex = middleIndex + 1;弥补了这一问题，使得程序需要再算一次才能确认endIndex是否匹配，同时与 endIndex = middleIndex - 1 一样，这样做可以减少查找的次数。
写一段用于验证的代码

    for (let i = 0; i <= 20; i++) {
      console.group(`长度为${i}的数组开始`);
      let arr = [];
      for (let j = 0; j < i; j++) {
        arr[j] = j;
      }
      arr.forEach((el) => {
        console.group(`查找元素${el}开始`);
        let index = binarySearch(el, arr);
        console.log(`位置为${index}`);
        console.assert(!(index === -1 || arr[index] !== el), "没找到");
        console.groupEnd(`查找元素${el}结束`);
      });
      let noFound = binarySearch(-1, arr);
      console.assert(noFound === -1, "未找到元素返回值不为-1");
      console.groupEnd(`长度为${i}的数组结束`);
    }

endIndex = middleIndex - 1;还是endIndex = middleIndex ;都能通过测试，
当查找的数偏向左侧时会起到作用，已长度为20，查找0为例

endIndex = middleIndex ;为5次
endIndex = middleIndex - 1 ;为4次
然而并非数组越长越明显，长度为200000，查找0也是少一次

while循环再编写过程中很容易卡死，看一下递归的解法:

    function binarySearch(argTarget, argArry) {
      function deal(startIndex, endIndex) {
        let middleIndex = ((startIndex + endIndex) / 2) | 0;
        let number = argArry[middleIndex];
        if (number === argTarget) {
          return middleIndex;
        } else if (number > argTarget) {
          endIndex = middleIndex - 1;
        } else {
          startIndex = middleIndex + 1;
        }
        if (startIndex <= endIndex) {
          return deal(startIndex, endIndex);
        }
      }
      let index = deal(0, argArry.length - 1);
      return index === undefined ? -1 : index;
    }

考虑倒序的情况:
测试函数在查找前加上arr.reverse();

    function binarySearch(argTarget, argArry) {
      let isReverse = argArry[0] > argArry[1];
      function deal(startIndex, endIndex) {
        let middleIndex = ((startIndex + endIndex) / 2) | 0;
        let number = argArry[middleIndex];
        if (number === argTarget) {
          return middleIndex;
        } else if (number > argTarget) {
          isReverse
            ? (startIndex = middleIndex + 1)
            : (endIndex = middleIndex - 1);
        } else {
          isReverse
            ? (endIndex = middleIndex - 1)
            : (startIndex = middleIndex + 1);
        }
        if (startIndex <= endIndex) {
          return deal(startIndex, endIndex);
        }
      }
      let index = deal(0, argArry.length - 1);
      return index === undefined ? -1 : index;
    }

argArry[0] > argArry[1] 当数组长度为1时，结果并不重要，要么匹配返回位置，要么结束匹配。

至于空数组的情况可以归纳为无效输入的场景。