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