二分查找
程序员文章站
2024-01-24 13:27:34
数组元素的查找 1. 线性查找方式 假如我们要在一个数组中找一个关键字key,可能浮现在大家脑海中的第一个方法就是一个for()循环进行线性查找,但是这种查找方式在数组元素个数很大的时候会很低效。原因如下: 该方法的执行时间随着数组个数的增长而线性增长 时间复杂度为O(n) 2. 二分查找法 具体实 ......
数组元素的查找
1. 线性查找方式
假如我们要在一个数组中找一个关键字key,可能浮现在大家脑海中的第一个方法就是一个for()循环进行线性查找,但是这种查找方式在数组元素个数很大的时候会很低效。原因如下:
- 该方法的执行时间随着数组个数的增长而线性增长
- 时间复杂度为O(n)
2. 二分查找法
具体实现步骤
前提:
数组必须被提前排好序了
- 若关键字小于中间元素则在前一半元素继续查找
- 若关键字大于中间元素则在后一半元素继续查找
- 若关键字等于中间元素,则匹配成功,查找结束
时间复杂度
假设有n个元素长度的数组,进行第一次比较后还需要比较n/2个元素;第二次比较后,还需要比较n/2/2个元素;经过第k次比较后,还需要比较n/2^k个元素。当k=log2n时,还需要比较一个元素。所以总共的比较次数最坏情况下是:log2n+1。故时间复杂度为O(log2n+1)。
3. 源码描述
public class BinarySearch{ public static binarySearch(int[] a,int key){ int low = 0; int high = a.length; while(low >= high){ int mid = (low+high)/2; if(key > a[mid]){ low = mid + 1; } else if(key == a[mid]) return mid; else high = mid - 1; } return -low-1; //返回该查找应该插入的下标位置 } }
补充:
选择排序:
每次把第i个元素,与后面length-i个元素进行比较,把最小的元素位置和i号元素位置进行对调。
public static void selectSort(int[] a){ //将每个元素和后面的所有元素进行比较,最小的放在第一个 for(int i = 0;i < a.length-1;i++){ int currentMin = a[i]; int currentIndex = i; for(int j = i+1;j < a.length;j++){ if(currentMin > a[j]){ currentMin = a[j]; currentIndex = j; } } //最小元素不是本身则对调 if(j!=i){ a[j] = a[i]; a[i] = currentMin; } } }
当然java.util.Arrays类有binarySearch()函数也可以实现二分查找的功能,但是对于初学者而言,了解其思想还是十分有必要的。
上一篇: spring 事物传播的一些易错点
下一篇: PHP执行系统命令函数实例讲解