Welcome everyone

每周一练(3)

每周一练 汪明鑫 257浏览 0评论

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

依赖于有序的顺序表(数组)

 

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

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

 

普通二分查找算法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)

喜欢 (0)

说点什么

您将是第一位评论人!

提醒
avatar
wpDiscuz