【15】-java实现二分查找

时间:2024-04-15 18:37:34

二分查找在面试中经常被遇到,这个方法十分优雅

介绍

二分查找可以解决(预排序数组的查找)问题:只要数组中包含T(即要查找的值),那么通过不断缩小包含T的范围,最终就可以找到它。一开始,范围覆盖整个数组。将数组的中间项与T进行比较,可以排除一半元素,范围缩小一半。就这样反复比较,反复缩小范围,最终就会在数组中找到T,或者确定原以为T所在的范围实际为空。对于包含N个元素的表,整个查找过程大约要经过log(2)N次比较。(引自编程珠玑)

趣闻

Jon Bentley:90%以上的程序员无法正确无误的写出二分查找代码。

java代码

public int binary_search(int[] array,int n,int value){
        //对空值进行判断
        if(array == null || n < 1){
            return -1;
        }
        int prev = 0;
        int end = n-1;
        while(prev <= end){
            int middle = prev +(end-prev)/2;
            if(array[middle] > value){
                end = middle-1;
            }else if(array[middle] < value){
                prev = middle +1;
            }else{
                return middle;
            }
        }
        return  -1;
    }

注意

如果end 一开始赋值n,后面代码需要相应的修改

  • while(prev < end)

    -当array[middle] > value的时候, end = middle;

递归写法

public static int search1(int[] array, int low, int high, int value) {
        //对空值进行判断
        if(array == null || low > high){
            return -1;
        }
        if(low <= high){
             int mid = (low + high) / 2;
        if (array[mid] == value) {
            return mid;
        } else if (array[mid] < value) {
            return search1(array, mid + 1, high, value);
        } else {
            return search1(array, low, mid - 1, value);
        }
     }else{
        return -1;
    }
    }    

欢迎入群:

公众号IT面试题汇总讨论群

【15】-java实现二分查找

如果扫描不进去,加我微信(rdst6029930)拉你。

扫我微信二维码加我

【15】-java实现二分查找

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧,都是干货!

微信订阅号二维码如下:

【15】-java实现二分查找