二分法查找

目录

二分法查找

介绍二分法查找

二分法的查找思路

二分法有关示例

解题思路

代码实现

二分法查找

介绍二分法查找

二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。

时间复杂度：

最坏情况查找结果为最后一个元素（或者第一个元素）T(n)=T(n/2)+O(1)所以T(n)=O(log2n)

最好情况O(1)所要查找的元素即为中间元素（奇数长度数列的正中间，偶数长度数列的中间靠左的元素）

空间复杂度     S(n)=logn

二分法的查找思路

1、首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。

2、如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤一的操作，进行递归查找。

3、如果某一步数组为空，则表示找不到目标元素。

二分法有关示例

解题思路

例如，在有序数据 [26，30，45，55，60，61，62，65，70，78，99] 中查找 55 的过程

代码实现

需要注意的是：在使用二分法之前要将数组进行排序，二分法针对的是有序数组。

非递归算法

function binarySearch(arr,key){
    var low=0; //数组最小索引值
    var high=arr.length-1; //数组最大索引值
    while(low<=high){
        var mid=Math.floor((low+high)/2);
        if(key==arr[mid]){
            return mid;
        }else if(key>arr[mid]){
            low=mid+1;
        }else{
            high=mid-1;
        }
    }
    return -1;  //low>high的情况，这种情况下key的值大于arr中最大的元素值或者key的值小于arr中最小的元素值
}

实现结果

递归算法 

function binarySearch(arr,low,high,key){
    if(low>high){
      return -1;
    }
    var mid=Math.floor((low+high)/2);
    if(key==arr[mid]){
        return mid;
    }else if(key<arr[mid]){
        high=mid-1;
        return binarySearch(arr,low,high,key);
    }else{
        low=mid+1;
        return binarySearch(arr,low,high,key);
    
    }   

 实现结果