算法图解——の——二分查找【附带pdf下载链接】

末蓝、 2022-11-11 14:48 136阅读 0赞

1、二分查找要求输入集合有序，所以好多算法会涉及到排序

2、二分查找效率高，用二分查找最多需要log 2 n步，而简单查找最多需要n步

举例说下，例如1.2.3......1024,二分查找最多需要log2 1024即10次，而普通查找最多需要1024次，发现有100倍的差距，数量越大，越明显

链接：**[https://pan.baidu.com/s/1V4rsYsFvwS745E05Cj5ZEQ ][https_pan.baidu.com_s_1V4rsYsFvwS745E05Cj5ZEQ]**  
提取码：**x7y4 **  
复制这段内容后打开百度网盘手机App，操作更方便哦--来自百度网盘超级会员V5的分享

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pwMzU3MjUyNTM5_size_16_color_FFFFFF_t_70][]

下面列出二分查找的java代码供参考，两个 不同的区别是，如果输入集合只有一个时，的代码拆分与整合。

/**
     * Created by burns.
     *
     * @author <a href="http://www.esoon-soft.com/">burns</a>
     * @date 2021/03/21 8:58
     */
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 二分查找
     *
     * @ClassName BinarySearch
     * @Author Burns
     * @DAte 2021/3/21 8:58
     */
    public class BinarySearch {
    
        public static void main(String[] args){
            {
                //第一种情况，传入的list为空
                System.out.println("第一种情况------start-------");
                List<Integer> list1 = null;
                int index = binarySearch(list1,0);
                outputInfo(index);
                System.out.println("第一种情况------end-------");
            }
    
    
            {
                //第二种情况，传递的list只有一个值
                System.out.println("第二种情况------start-------");
                List<Integer> list2 = new ArrayList<Integer>();
                list2.add(1);
                int index = binarySearch(list2,1);
                outputInfo(index);
                System.out.println("第二种情况------end-------");
            }
    
            {
                //第三种情况，传递的list有多个值
                System.out.println("第三种情况------start-------");
                List<Integer> list3 = new ArrayList<Integer>();
                list3.add(1);
                list3.add(2);
                list3.add(3);
                list3.add(4);
                list3.add(5);
                int index = binarySearch(list3,3);
                outputInfo(index);
                System.out.println("第三种情况------end-------");
            }
    
    //        其中 第二和第三种情况可以合并在一起，区别是 while (low<high)改成 while (low<=high){
    
        }
    
        private static void outputInfo(int index) {
            if(index==-1){
                System.out.println("没找到");
            }else {
                System.out.println("找到了，序列是"+index);
            }
        }
    
        /**
         * 三种情况分开
         *
         * @Description:
         * @Param: [list, n]
         * @Return: int
         * @Author: Burns
         * @Date: 2021/3/21
         */
    
        private static int binarySearch(List<Integer> list,int n){
            if(list == null || list.size()==0){
                System.out.println("输入集合为空！");
                return -1;
            }else {
    
                if(list.size()==1){
                    if(n==list.get(0)){
                        return 0;
                    }else {
                        System.out.println("没找到！");
                        return -1;
                    }
                }else {
    
                    //定义开头和结尾部分要查找的位置序号,list的第一个值是从0开始的，所以high就是list的数量-1
                    int low = 0;
                    int high = list.size()-1;
    
                    //如果low小于等于high,说明值还没有找到，需要继续找，否则
                    while (low<high){
                        int mid = (low+high)/2;
                        //猜测值为中间的值
                        int guess = list.get(mid);
                        //如果猜测值和中间值相等，则返回
                        if(guess==n){
                            return mid;
                        }
                        //如果猜测值比查找值大
                        if(guess>n){
                            high = mid-1;
                        }else {
                            low = mid+1;
                        }
                    }
                    return -1;
                }
            }
        }
    
    
    }

/**
     * Created by burns.
     *
     * @author <a href="http://www.esoon-soft.com/">burns</a>
     * @date 2021/03/21 8:58
     */
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 二分查找
     *
     * @ClassName BinarySearch
     * @Author Burns
     * @DAte 2021/3/21 8:58
     */
    public class BinarySearch1 {
    
        public static void main(String[] args) {
            {
                //第一种情况，传入的list为空
                System.out.println("第一种情况------start-------");
                List<Integer> list1 = null;
                int index = binarySearch(list1, 0);
                outputInfo(index);
                System.out.println("第一种情况------end-------");
            }
    
    
            {
                //第二种情况，传递的list只有一个值
                System.out.println("第二种情况------start-------");
                List<Integer> list2 = new ArrayList<Integer>();
                list2.add(1);
                int index = binarySearch(list2, 1);
                outputInfo(index);
                System.out.println("第二种情况------end-------");
            }
    
            {
                //第三种情况，传递的list有多个值
                System.out.println("第三种情况------start-------");
                List<Integer> list3 = new ArrayList<Integer>();
                list3.add(1);
                list3.add(2);
                list3.add(3);
                list3.add(4);
                list3.add(5);
                int index = binarySearch(list3, 3);
                outputInfo(index);
                System.out.println("第三种情况------end-------");
            }
    
    //        其中 第二和第三种情况可以合并在一起，区别是 while (low<high)改成 while (low<=high){
    
        }
    
        private static void outputInfo(int index) {
            if (index == -1) {
                System.out.println("没找到");
            } else {
                System.out.println("找到了，序列是" + index);
            }
        }
    
        /**
         * 三种情况分开
         *
         * @Description:
         * @Param: [list, n]
         * @Return: int
         * @Author: Burns
         * @Date: 2021/3/21
         */
    
        private static int binarySearch(List<Integer> list, int n) {
            if (list == null || list.size() == 0) {
                System.out.println("输入集合为空！");
                return -1;
            } else {
    
    
                //定义开头和结尾部分要查找的位置序号,list的第一个值是从0开始的，所以high就是list的数量-1
                int low = 0;
                int high = list.size() - 1;
    
                //如果low小于等于high,说明值还没有找到，需要继续找，否则
                while (low <= high) {
                    int mid = (low + high) / 2;
                    //猜测值为中间的值
                    int guess = list.get(mid);
                    //如果猜测值和中间值相等，则返回
                    if (guess == n) {
                        return mid;
                    }
                    //如果猜测值比查找值大
                    if (guess > n) {
                        high = mid - 1;
                    } else {
                        low = mid + 1;
                    }
                }
                return -1;
            }
        }
    
    
    }

[https_pan.baidu.com_s_1V4rsYsFvwS745E05Cj5ZEQ]: https://pan.baidu.com/s/1V4rsYsFvwS745E05Cj5ZEQ%C2%A0
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pwMzU3MjUyNTM5_size_16_color_FFFFFF_t_70]: /images/20221022/93e73d1172454389ab6a18b1efcb1948.png