二分查找可以说是我们最早接触的算法之一

依赖于有序的顺序表（数组）

二分查找不适用数据太小的，太小的数据直接顺序遍历就完事

也不适合数据太大的，数组需要一片连续的内存空间

普通二分查找算法code

//普通二分查找
    public static int search(int[] a, int n, int target){
        int low = 0;
        int high = n-1;
        while(low <= high){
            int mid = (low+high)/2;
            if(a[mid] < target){
                low = mid + 1;
            }else if(a[mid] > target){
                high = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

一些二分查找的变形题（近似搜索）

• 查找第一个等于某值的
• 查找最后一个等于某值的
• 查找第一个大于等于某值的
• 查找最后一个小于等于某值的

完整代码如下，关键地方我已经添加了注释：

package pers.wmx.practice.search;

/**
 * @author wmx
 * @date 2019-12-11
 */
public class MyBinarySearch {

    //普通二分查找
    public static int search(int[] a, int n, int target){
        int low = 0;
        int high = n-1;
        while(low <= high){
            int mid = (low+high)/2;
            if(a[mid] < target){
                low = mid + 1;
            }else if(a[mid] > target){
                high = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

    //查找第一个等于的
    public static int searchFirstEqual(int[] a, int n, int target){
        int low = 0;
        int high = n-1;
        while(low <= high){
            int mid = (low+high)/2;
            if(a[mid] < target){
                low = mid + 1;
            }else if(a[mid] > target){
                high = mid - 1;
            }else {  //已经找到等于，但不一定是第一个等于的，所以需要往前一个看一看
                //如果mid已经到0了或者mid前面没有等于目标值得
                if(mid == 0 || a[mid-1]!=target){
                    return mid;
                }else {
                    high = mid -1;
                }
            }
        }
        return -1;
    }

    //查找最后一个等于的
    public static int searchLastEqual(int[] a, int n, int target){
        int low = 0;
        int high = n-1;
        while(low <= high){
            int mid = (low+high)/2;
            if(a[mid] < target){
                low = mid + 1;
            }else if(a[mid] > target){
                high = mid - 1;
            }else {  
                //如果mid已经到n-1了或者mid后面没有等于目标值得
                if(mid == n-1 || a[mid+1]!=target){
                    return mid;
                }else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }

    //查找第一个大于等于的
    public static int searchFirstLarge(int[] a, int n, int target){
        int low = 0;
        int high = n-1;
        while(low <= high){
            int mid = (low+high)/2;
            if(a[mid] < target){
                low = mid + 1;
            }else {  //大于等于的
                if(mid == 0 || a[mid-1] < target){  //往前看一位，确定自己是第一个
                    return  mid;
                }else{
                    high = mid - 1;   //不是第一个，说明前面还有等于目标值的，high左移
                }
            }
        }
        return -1;
    }

    //查找最后一个小于等于的
    public static int searchLastSmall(int[] a, int n, int target){
        int low = 0;
        int high = n-1;
        while(low <= high){
            int mid = (low+high)/2;
            if(a[mid] > target){
                high = mid - 1;
            }else { //小于等于的
                if(mid == n-1 || a[mid+1] > target){  //往后看一位，确定自己是最后一个
                    return  mid;
                }else{   
                    low = mid + 1;   //不是最后一个，low右移
                }
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        int[] a = {1,3,5,7,9,11,13};
        System.out.println(search(a,a.length,9));


        int[] a1 = {1,3,5,7,9,9,9,9,11,13};
        System.out.println(searchFirstEqual(a1,10,9));  //4
        System.out.println(searchLastEqual(a1,10,9));   //7
        System.out.println(searchFirstLarge(a1,10,9));  //4
        System.out.println(searchLastSmall(a1,10,9));   //7
    }

}

转载请注明：汪明鑫的个人博客 » 每周一练（3）