js 快速查找字符在数组集合中出现的位置之二分法

作者: tww844475003 分类: 前端开发 发布时间: 2021-07-06 19:35

二分法

固名思义,一分为二,从中间开始查

条件

采用二分法查找数据集合必须是有序的

实现思路

循环,首页取出数据集合最中间的值,比较这个值与要查找的值的大小

  • currentKey === findKey,当然就等到结果了
  • currentKey > findKey,由于是有序数据集合,就只需要查开始位置=》这个值之前的数据,重新这个新的数据集合中二分
  • currentKey < findKey,由于是有序数据集合,就只需要查这个值之后的数据=》末尾数据,重新这个新的数据集合中二分
function strFastSearch(arr, key) {
      var low = 0;
      var high = arr.length - 1;

      while (low <= high) {
        var mid = parseInt((high + low) / 2);

        if (key === arr[mid]) {
          return mid;
        } else if (key > arr[mid]) {
          low = mid + 1;
        } else if (key < arr[mid]) {
          high = mid - 1;
        } else {
          return -1;
        }
      }
    }

    var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    var result = strFastSearch(arr, 9);
    console.log(result)
前端开发那点事
微信公众号搜索“前端开发那点事”

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注