Java实现二分查找，查询数组中的元素

曾经终败给现在 2023-01-07 10:10 145阅读 0赞

### 折半查找法 ###

*  折半查找法
 *   *  具体实现
     *   *  1、主函数内部实现
         *  2、定义方法，并调用：
         *  3、调用Arrays中的binarySearch方法：
     *  总结

# 折半查找法 #

折半搜索（英语：half-interval search），也称二分搜索（英语：binary search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。  
**搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。**这种搜索算法每一次比较都使搜索范围缩小一半。

## 具体实现 ##

### 1、主函数内部实现 ###

源代码：

import java.util.Scanner;
    /** * Java实现二分查找 */
    public class binarySearchDemo { 
        public static void main(String[] args) { 
            //定义一个数组，并初始化
            int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
            Scanner sc = new Scanner(System.in);
            //输入你要查找的数字。
            int key = sc.nextInt();
            int left = 0;
            int right = arr.length - 1;
            int mid=0;
            while (left <= right) { 
                mid = (left + right) / 2;
                if (arr[mid] < key) { 
                    left = mid + 1;
                } else if (arr[mid] > key) { 
                    right = mid - 1;
                } else { 
                   break;
                }
            }
            if (left <= right) { 
                System.out.println("找到了，下标是：" + mid);
            } else { 
                System.out.println("未找到！");
            }
        }
    }

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]

### 2、定义方法，并调用： ###

定义方法，并调用方法，找到查找的数字，则返回下标，未找到，则返回-1（数组的下标不可能为负数）

源代码：

import java.util.Scanner;
    
    /** * 二分查找方法实现 */
    public class binarySearchDemo1 { 
        public static int myBinarySearch(int[] arr, int key) { 
            int left = 0;
            int right = arr.length - 1;
            int mid = 0;
            while (left <= right) { 
                mid = (left + right) / 2;
                if (arr[mid] < key) { 
                    left = mid + 1;
                } else if (arr[mid] > key) { 
                    right = mid - 1;
                } else { 
                    break;
                }
            }
            if (left <= right) { 
                //如果找到，返回下标
                return mid;
            } else { 
                //如果没找到，返回-1
                return -1;
            }
        }
        
        public static void main(String[] args) { 
            //定义一个数组，并初始化
            int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
            Scanner sc = new Scanner(System.in);
            //输入你要查找的数字。
            int key = sc.nextInt();
            System.out.println(myBinarySearch(arr, key));
    
        }
    }

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]

### 3、调用Arrays中的binarySearch方法： ###

在Java中提供了很多的方法，其中Arrays是对数组的操作方法，binarySearch可以实现二分查找，但是在使用的时候需要导入包：import java.util.Arrays;

binarySearch方法有各种类型的：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 4]

源代码：

import java.util.Arrays;
    import java.util.Scanner;
    
    /** * 调用Arrays中的binarySearch方法 */
    public class binarySearchDemo2 { 
    
        public static void main(String[] args) { 
            //定义一个数组，并初始化
            int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
            Scanner sc = new Scanner(System.in);
            //输入你要查找的数字。
            int key = sc.nextInt();
            //调用方法：
            System.out.println(Arrays.binarySearch(arr, key));
        }
    }

运行结果：  
![在这里插入图片描述][20210116194728205.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 5]

## 总结 ##

虽然这种方法很简便，大大加快了我们解题速度，但是作为初学者，还是需要弄懂其原理！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210116193501300.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]: /images/20221119/1f9c91d5ba254b9db747fa36376d3d75.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]: /images/20221119/301ec69774d14f9aad1b68068f7e3758.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]: /images/20221119/6ae8ad81f54f418cba7efecf1fe7a4a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 4]: /images/20221119/8c2da37c62ac4e58ba461dbe26c57ce0.png
[20210116194728205.png]: /images/20221119/375f04a981a443ca8908a81349db4f6a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 5]: /images/20221119/29e5132404a046139a6ed0868aa61bb7.png