JavaScript 中的二分查找

JavaScriptJavaScriptBeginner
立即练习

This tutorial is from open-source community. Access the source code

💡 本教程由 AI 辅助翻译自英文原版。如需查看原文,您可以 切换至英文原版

简介

在本实验中,我们将探索 JavaScript 编程的基础知识。我们将涵盖变量、数据类型、函数和控制流等主题。在实验结束时,你将对 JavaScript 语法有扎实的理解,并能够使用该语言编写基本程序。本实验是为几乎没有编程经验的初学者设计的,但对于那些想要复习 JavaScript 知识的人来说也会很有用。


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL javascript(("`JavaScript`")) -.-> javascript/BasicConceptsGroup(["`Basic Concepts`"]) javascript/BasicConceptsGroup -.-> javascript/variables("`Variables`") javascript/BasicConceptsGroup -.-> javascript/data_types("`Data Types`") javascript/BasicConceptsGroup -.-> javascript/arith_ops("`Arithmetic Operators`") javascript/BasicConceptsGroup -.-> javascript/comp_ops("`Comparison Operators`") javascript/BasicConceptsGroup -.-> javascript/cond_stmts("`Conditional Statements`") javascript/BasicConceptsGroup -.-> javascript/loops("`Loops`") javascript/BasicConceptsGroup -.-> javascript/array_methods("`Array Methods`") subgraph Lab Skills javascript/variables -.-> lab-28173{{"`JavaScript 中的二分查找`"}} javascript/data_types -.-> lab-28173{{"`JavaScript 中的二分查找`"}} javascript/arith_ops -.-> lab-28173{{"`JavaScript 中的二分查找`"}} javascript/comp_ops -.-> lab-28173{{"`JavaScript 中的二分查找`"}} javascript/cond_stmts -.-> lab-28173{{"`JavaScript 中的二分查找`"}} javascript/loops -.-> lab-28173{{"`JavaScript 中的二分查找`"}} javascript/array_methods -.-> lab-28173{{"`JavaScript 中的二分查找`"}} end

二分查找算法

要开始编码练习,请打开终端/SSH 并输入 node。二分查找算法用于在已排序的数组中找到给定元素的索引。以下是实现二分查找算法的步骤:

  1. 声明左边界和右边界 lr,分别初始化为 0 和数组的 length
  2. 使用 while 循环,通过使用 Math.floor() 将搜索子数组一分为二来反复缩小搜索范围。
  3. 如果找到元素,则返回其索引。否则,返回 -1
  4. 请注意,此算法不考虑数组中的重复值。

以下是 JavaScript 中二分查找算法的示例实现:

const binarySearch = (arr, item) => {
  let l = 0,
    r = arr.length - 1;
  while (l <= r) {
    const mid = Math.floor((l + r) / 2);
    const guess = arr[mid];
    if (guess === item) return mid;
    if (guess > item) r = mid - 1;
    else l = mid + 1;
  }
  return -1;
};

你可以使用以下示例测试 binarySearch 函数:

binarySearch([1, 2, 3, 4, 5], 1); // 0
binarySearch([1, 2, 3, 4, 5], 5); // 4
binarySearch([1, 2, 3, 4, 5], 6); // -1

总结

恭喜你!你已经完成了二分查找实验。你可以在 LabEx 中练习更多实验来提升你的技能。

您可能感兴趣的其他 JavaScript 教程