Java算法：二分查找

末蓝、 2024-02-20 12:11 61阅读 0赞

#### 一、 二分查找注意 ####

**前提**是数组必须是**有序的**，否则无法正常工作。如果数组**不是有序**的，需要先**对数组进行排序**，然后才能使用二分查找算法。

#### 二、二分查找高效算法 ####

二分查找也称为**折半查找**，是一种在**有序数组**中查找目标元素的算法。它的原理是不断将查找范围减半，直到找到目标元素或确定目标元素不存在。

在一个有序数组中查找特定元素时，二分查找是一种高效的算法。它的时间复杂度为 O(log n)，相较于线性查找的 O(n)，二分查找可以显著提高搜索效率。

#### 三、二分查找步骤 ####

> 初始化左边界 left 为数组第一个元素的索引，右边界 right 为数组最后一个元素的索引。  
> 计算中间元素的索引 mid=(left + right) / 2。  
> 比较中间元素与目标元素：  
> 如果中间元素=目标元素，则找到目标，返回中间元素的索引。  
> 如果中间元素>目标元素，则将右边界更新为 mid - 1，继续在左半边查找。  
> 如果中间元素<目标元素，则将左边界更新为 mid + 1，继续在右半边查找。

#### 四、 Java 实现二分查找 ####

//测试数据
        public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            List<Integer> list = getList();
            System.out.println(list);
            while(true) {
                System.out.print("输入查找的数字：");
                int find_num = sc.nextInt();
                Integer num = search(list, find_num);
                System.out.println(num);
            }
        }
    
        /**
         * （2）二分查找法：
         * @param list
         * @param number
         * @return
         */
        private static Integer search(List<Integer> list, int number) {
            //左边位置
            int low = 0;
            //右边位置
            int high = list.size() - 1;
            //循环
            while (low <= high) {
                //中间元素
                int mid = (low + high) / 2;
                //获取中间元素
                int guess = list.get(mid);
                //判断
                if (guess == number) { //找到这个元素
                    return mid;
                } else if (guess > number) { //中间元素大于输入的目标数据,继续在left半边查找
                    high = mid - 1;
                } else {  //中间元素小于输入的目标数据,继续在right半边查找
                    low = mid + 1;
                }
            }
            return -1;  //找不到元素，则返回-1
        }
    
        /**
         * （1） 有序列表数据20个随机生成
         */
        private static List<Integer> getList() {
            //过滤重复的数据
            Set<Integer> sets = new HashSet<>();
            Random random = new Random();
            while (true) {
                //生成1-50的随机数
                int ran = random.nextInt(50) + 1;
                //添加
                sets.add(ran);
                //判断生成20个数据
                if (sets.size() >= 20) {
                    break;
                }
            }
            //集合数据
            List<Integer> list = new ArrayList<>(sets);
            //升序排序
            Collections.sort(list);
            return list;
        }

**效果：**

![9fc7d03717d64870bb4a5809031ad252.png][]

#### 优点和缺点 ####

二分查找算法的主要**优点**是其**时间复杂度为O(log n)**，因此对于大型数组的查找操作非常高效。此外，由于二分查找是基于数组的有序性进行查找的，因此可以应用于静态数据集合中的查找操作。

二分查找也存在一些明显的缺点。**首先**，二分查找只适用于有序数组，因此如果需要在无序的数据集中查找元素，则需要事先对数据进行排序。**其次**，二分查找**不适用于动态数据结构，因为在插入或删除元素后，会破坏数组的有序性，需要重新排序才能再次使用二分查找**。

[9fc7d03717d64870bb4a5809031ad252.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/93da77eeecd1406e97046765a6aa9820.png