手记

【九月打卡】第21天 算法(4)

课程名称2周刷完100道前端优质面试真题
课程章节:第2章 前端面试技能拼图1 :数据结构和算法(上),大厂面试必考
主讲老师双越
课程内容
今天学习的内容包括:
2-15 用 JS 实现二分查找-分析时间复杂度
2-16 用 JS 实现二分查找-代码演示和单元测试
2-17 用 JS 实现二分查找-递归和循环哪个更好
这几节主要是讲二分查找是啥,时间复杂度,两种实现方式和比较。

课程收获
主要内容大致复述如下。

  • 二分查找

用于已排序的数据。

假设表中元素是按升序排列,中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

  • 循环写法

这个非常常见了,基本按照定义写就行。注意取中间值的 Math.floor 和 边界判断。

  const search = (arr, target) => {
    const len = arr.length;
    if (len) {
      let l = 0, r = len - 1;
      while (l <= r) {
        let mid = Math.floor((l + r) / 2);
        if (target === arr[mid]) {
          return mid;
        } else if (target > arr[mid]) {
          l = mid + 1;
        } else {
          r = mid - 1;
        }
      }
      return -1;
    } else {
      return -1;
    }
  };
  const arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120];
  const target = 40;
  console.info("二分结果", search(arr, target));
  • 递归写法

每次比较中间位置记录的关键字与查找关键字,如果不相等,则修改范围再次调用。

  const search1 = (arr, target, l, r) => {
    const len = arr.length;
    if (!len || l > r) return -1;
    if (l == null) l = 0;
    if (r == null) r = len - 1;
    const m = Math.floor((l + r) / 2);
    if (target === arr[m]) {
      return m;
    } else if (target > arr[m]) {
      return search1(arr, target, m + 1, r);
    } else {
      return search1(arr, target, l, m - 1);
    }
  };
  • 递归和循环哪个快

时间复杂度都是O(logn)
console.time 实际测试结果循环更快
原因:递归增加了函数调用次数。

以上,结束。

0人推荐
随时随地看视频
慕课网APP