二分查找算法

  1. 前提条件:一个有序的数组
    const arr=[ 33, 44, 55, 55, 78, 88, 99, 101, 110, 115, 120, 125, 130, 140, 150, 166 ];

  2. 问题:查找其中是否包含指定数字n?
    解决方法1.
    用普通查找法,算法复杂度O(n).

const normal_search = (arr,n)=>{
   let i=0;
   while (i<arr.length){
     console.log("普通查找走了一次",i,arr[i],n);
     if(arr[i]===n){
       return i
     }
       i+=1;
   }
   return -1
 };
 console.log("普通查找",arr,normal_search(arr,99));

解决方法2.
用二分查找法,算法复杂度O(log n).

  const binary_search=(arr,n)=>{
    const binary_search_copy=(arr,n,start,end)=>{
      console.log("二分查找走了一次");
      if(arr.length<1){return -1};
      let middle = Math.floor((start+end)/2);
      if(n===arr[middle]){
        return middle
      }else if(n<=arr[middle]){
        return binary_search_copy(arr,n,start,middle-1)
      }else if(n>arr[middle]){
        return binary_search_copy(arr,n,middle+1,end)
      }
    };
    return  binary_search_copy(arr,n,0,arr.length)
  };
  console.log("二分查找",arr,binary_search(arr,99)); // 6
  console.log("二分查找",arr,binary_search(arr,166)); // 15
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 如下代码内容是关于C++实现二分查找算法的的代码。 < >= template< typename T, type...
    食蚁兽族阅读 701评论 0 0
  • 可查找重复元素的二分查找算法 二分查找算法思想:又称为 折半查找,二分查找适合对已经排序好的数据集合进行查找。假设...
    奇迹迪阅读 3,998评论 5 5
  • 算法描述: 二分查找(binary search),也称折半搜索,是一种在有序数组中查找某一特定元素的搜索算法。 ...
    Albert84阅读 177评论 0 0
  • 我是黑夜里大雨纷飞的人啊 1 “又到一年六月,有人笑有人哭,有人欢乐有人忧愁,有人惊喜有人失落,有的觉得收获满满有...
    陌忘宇阅读 8,607评论 28 53
  • 信任包括信任自己和信任他人 很多时候,很多事情,失败、遗憾、错过,源于不自信,不信任他人 觉得自己做不成,别人做不...
    吴氵晃阅读 6,231评论 4 8