JS二分查找实现及时间复杂度

迷南。 2022-11-07 01:56 161阅读 0赞

二分法查找，也称折半查找，是一种在**有序数组**中查找特定元素的搜索算法。查找过程可以分为以下步骤：  
（1）首先，从有序数组的**中间**的元素开始搜索，如果该元素正好是目标元素（即要查找的元素），则搜索过程结束，否则进行下一步。  
（2）如果目标元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作。  
（3）如果某一步数组为空，则表示找不到目标元素。

###  非递归 ###

//非递归
      function search(arr,key) {
        let min = 0
        let max = arr.length-1
        while (min<=max) {
          let mid = parseInt((min+max)/2)
          if(key == arr[mid]){
            return mid
          }else if(key>mid){
            min=mid+1
          }else if(key<mid){
            max=mid-1
          }else{
            return -1
          }
        }
      }
      var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
      var result = search(arr,10);
      alert(result); // 9 返回目标元素的索引值

### 递归 ###

//递归
      function  search(arr,key,min,max) {
        var mid=parseInt((min+max)/2)
        if(key == arr[mid]){
            return mid
          }else if(key>mid){
            min=mid+1
            return search(arr,key,min,max)
          }else if(key<mid){
            max=mid-1
            return search(arr,key,min,max)
          }else{
            return -1
          }
      }
      var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
      var result = search(arr, 10, 0, 13);
      alert(result); // 9 返回目标元素的索引值

### 时间复杂度 ###

假设总数据量是n,那二分查找无非就是用get（要查找的数）和n/2, n/4, n/8, ...... n/2^k进行比较，k是循环的次数

那么n/2^k <=1

那么我们令 n/2^k =1

k = log2(n)（是以2为底，n的对数）

那么这个T(n)，是小于等于，并且接近于函数fn=(logn)

所以时间复杂度为O()=O(logn)