Java算法:二分查找
一、 二分查找注意
前提是数组必须是有序的,否则无法正常工作。如果数组不是有序的,需要先对数组进行排序,然后才能使用二分查找算法。
二、二分查找高效算法
二分查找也称为折半查找,是一种在有序数组中查找目标元素的算法。它的原理是不断将查找范围减半,直到找到目标元素或确定目标元素不存在。
在一个有序数组中查找特定元素时,二分查找是一种高效的算法。它的时间复杂度为 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;}
效果:
优点和缺点
二分查找算法的主要优点是其时间复杂度为O(log n),因此对于大型数组的查找操作非常高效。此外,由于二分查找是基于数组的有序性进行查找的,因此可以应用于静态数据集合中的查找操作。
二分查找也存在一些明显的缺点。首先,二分查找只适用于有序数组,因此如果需要在无序的数据集中查找元素,则需要事先对数据进行排序。其次,二分查找不适用于动态数据结构,因为在插入或删除元素后,会破坏数组的有序性,需要重新排序才能再次使用二分查找。