二分搜索 / 折半查找

ゞ 浴缸里的玫瑰 2022-05-25 02:12 310阅读 0赞

查找/搜索算法中，顺序搜索没什么好说的，从二分搜索 / 折半查找开始。

步骤

  • 选择中间值 （low+high） / 2
  • 如果它是目标值，bingo~
  • 如果大了，从其左边的一半找
  • 如果小了，从其右边的一半找
  • 如果找不到，返回 -1 或 null 等

注意： 需要数组本身有序

递归实现

  1. function binaryhSearch(arr, low, high, target) { 
  2.   if (low > high) return null;
  3.   mid = Math.floor((low + high) / 2);
  4.   if (arr[mid] === target) return mid;
  5.   if (arr[mid] < target) {
  6.     return binaryhSearch(arr, mid + 1, high, target);
  7.   } else {
  8.     return binaryhSearch(arr, low, mid - 1, target);
  9.   }
  10. }

非递归实现

直接把 low high 用 mid +/- 1 替换

  1. function binaryhSearch(arr, low, high, target) {
  2.   while (low <= high) {
  3.     let mid = Math.floor((low + high) / 2);
  4.     if (arr[mid] === target) return mid;
  5.     if (arr[mid] < target) {
  6.       low = mid + 1;
  7.     } else {
  8.       high = mid - 1;
  9.     }
  10.   }
  11.   return null;
  12. }

发表评论

表情：
评论列表 （有 0 条评论，310人围观）

还没有评论，来说两句吧...

相关阅读

    相关 二分查找(折半查找)

    二分查找 了解B+树的时候，看到了二分查找，发现自己只知道名称的意思是折半查找，却不知道是怎么去实现的。 后来查阅网上资料，发现二分查找必须要求数据是有序的，这样就

    川长思鸟来川长思鸟来/ 0 赞/ 327 阅读

    相关 java实现二分查找（折半查找）

    算法思想：要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分

    Myth丶恋晨Myth丶恋晨/ 0 赞/ 337 阅读