Web前端之路优美编程

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

2020-03-16  本文已影响0人  小遁哥

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

二分法查找的思路如下:

(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;
    }

startIndexendIndex小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时,结果并不重要,要么匹配返回位置,要么结束匹配。

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

上一篇 下一篇

猜你喜欢

热点阅读