vlambda博客
学习文章列表

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

查找过程

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

算法复杂度

二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
时间复杂度即是while循环的次数。
总共有n个元素，
渐渐跟下去就是n,n/2,n/4,…n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数
由于你n/2^k取整后>=1
即令n/2^k=1
可得k=log2n,（是以2为底，n的对数）
所以时间复杂度可以表示O(h)=O(log2n)

编码举例

public class Demo1 {
    public static int getBinarySearch(int[] arrs,int num){
        int low = 0,high = arrs.length - 1;
        int mid;

        while(low <= high){
            mid = (low + high) / 2;
            if(num > arrs[mid]){
                low = mid + 1;
            }else if(arrs[mid] > num){
                high = mid - 1;
            }else {
                return arrs[mid];
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {6,12,33,87,90,108,561};
        int target = 90;

        int res = getBinarySearch(arr,target);

        if(res != -1){
            System.out.println("二分查找成功");
        }else {
            System.out.println("二分查找失败");
        }
    }
}

运算结果：

二分查找算法的应用

1、旋转数组查找最小值

public class Demo1 {
    /**
 * 查找旋转数组的最小数字
 * @param arr
 * @return
 */

    public static int minArrays(int[] arr){
        //使用二分查找法
        int low = 0,high = arr.length - 1;
        int mid;
        while (low < high){
            mid = (low + high) / 2;

            if(arr[mid] > arr[high]) low = mid + 1;
            else if(arr[mid] < arr[high]) high = mid;
            else high --;
        }
        return arr[high];
    }

    public static void main(String[] args) {
        int[] arrs = {4,5,6,7,0,1,2,3,};

        System.out.println("旋转数组的最小值为:"+minArrays(arrs));
    }
}

运行结果:

2、逆转数组

public class Demo1 {
    public static int[] reversePrint(int[] arr){
        int temp,low = 0,high = arr.length - 1;
        while(low < high){
            temp = arr[low];
            arr[low] = arr[high];
            arr[high] = temp;

            low ++;
            high --;
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arrs = {1,2,3,4,5,6,7,8,9,10};

        System.out.println("原数组为:");
        for(int num:arrs){
            System.out.print(num+"\t");
        }

        System.out.println("\n"+"逆转后的数组为:");
        for(int num:reversePrint(arrs)){
            System.out.print(num+"\t");
        }
    }
}

运算结果：

3、 查找第一个大于等于给定值的元素，即在递增数组中查找第一个大于某目标数字的数字和下标

public class Demo1 {
    /**
 * 查找第一个大于等于给定值的元素
 * 在递增数组中查找第一个大于某目标数字的数字和下标
 * @param arr
 * @return
 */
    public static int findNum(int[] arr,int target){
        int low = 0,high = arr.length - 1;
        int mid;

        while(low < high){
            mid = (low + high) / 2;
            if(arr[mid] < target){
                low  = mid + 1;
            }else {
                high = mid - 1;
            }
            return mid;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arrs = {1,2,3,4,5,6,7,8,9};
        int target = 5;

        if(findNum(arrs,target) == -1){
            System.out.println("未查找到目标元素。");
        }else{
            System.out.println("目标元素已找到\n下标是:"+findNum(arrs,target)+"\n对应元素是:"+arrs[findNum(arrs,target)]);
        }
    }
}

运算结果：