二分查找

前提

1. 必须是顺序存储结构
2. 必须按关键字大小有序排列

时间复杂度
​ O(log2n)

原理
​ 判断中位数mid跟key的关系，key>mid,则key在mid右边部分，于是取右边的中位数继续判断与key的关系，以此类推。

代码实现

public class BinarySearch{
    //
    public static int rank1(int key,int[] arr){
        int lo=0;
        int hi=arr.length-1;
        while(lo<hi){
            int mid=lo+(hi-lo)/2;
            if(arr[mid]<key) lo=mid+1;
            else if(arr[mid]>key) hi=mid-1;
            else return mid;
        }
        return -1;
    }

    //递归实现
    public static int rank2(int key,int[] arr){
        return rank2(key,arr,0,arr.length-1);
    }
    public static int rank2(int key,int[] arr,int lo,int hi){
        if(lo>hi) return -1;
        int mid=lo+(hi-lo)/2;
        if(arr[mid]<key) return rank2(key,arr,mid+1,hi);
        else if(arr[mid]>key) return rank2(key,arr,lo,mid-1);
        else return mid;
    }

    //
    public static int rank3(int key,int[] arr){
        int lo=0;
        int hi=arr.length-1;
        for(int i=lo;i<hi;i++){
            if(arr[lo+(hi-lo)/2]<key){
                lo=lo+(hi-lo)/2+1;
                continue;
            }else if(arr[lo+(hi-lo)/2]>key){
                hi=lo+(hi-lo)/2-1;
                continue;
            }else{
                return lo+(hi-lo)/2;
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        int[] ar={1,2,3,4,55,77,122,333345};
        int key1=2;
        int key2=5;
        System.out.println(rank3(key1, ar));
        System.out.println(rank3(key2, ar));
    }
}