二分法查找

基础知识

log2为底数的算法是:
LOG2(N)
相当于2的多少次方(立方)等于N
例:LOG2(8)=3
相当于,2的3次方等于8

二分法

从排序好的数组,找到你需要找到的值(t=1),算法复杂度:O(log2(n))

步骤:首先确认查找的数组索引范围,

1:假设数据int[] arr = {0,1,2,3,4,5,6,7,8,9};

2:则搜索范围为 [0,9];即int start =0;int end = 9;

3:取数组索引中间的值跟t比较,int middle = (start + end)/2=4;

4:如果arr[middle]>t;则搜索范围控制在了(0,middle-1],即 end = middle-1;

相反,arr[middle]<t;则搜索范围控制在(middle+1,9],则 start = middle+1;

5:如果arr[middle]=t,搜索结束,否则就重复3,4。

写法

java

非递归写法
//二分法搜索算法
    private Integer binary_search(int[] arr, int t) {
 
        int start = 0, end = arr.length - 1;//扫描范围
 
        while (start<=end){
            int mid = (end + start) / 2;//中间数索引位置
 
            if (t< arr[mid]){
                end = mid-1;
            }
            if (t>arr[mid]){
                start = mid+1;
            }
            if (t == arr[mid]){
                return mid;
            }
        }
        return null;
    }


递归写法
public static int search(int num,int low,int high,int a[]) {

    int middle = (high+low) / 2;

    while(low<=high){
    
        //注意等号要有
        
        if(a[middle]>num){
        
            return search(num, low, middle-1, a);
        
        }else if(a[middle]<num){
        
            return search(num, middle+1, high, a);
        
        }else{
        
            return middle;
        
        }
    
    }
    
    return-1;

}

js

非递归写法

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);
    }
}

站在巨人的肩膀上摘苹果:

原文链接:https://blog.csdn.net/u012194956/article/details/79103843
原文链接:https://blog.csdn.net/vacblog/article/details/80865715
原文链接: https://blog.csdn.net/dijiaxing1234/article/details/81178097

上一篇:css3基础---图片水平垂直居中


下一篇:PPT快捷键与操作技巧