二分查找是一种效率较高的查找方法,时间复杂度是O(logn)
二分查找:每次都通过跟区间中的中间元素对比,将待查找的区间缩小为一半,直到找到要查找的元素,或 者区间被缩小为0
使用前提:
- 二分查找必须依赖顺序表结构(数组)
- 二分查找查询的数据必须是有序的
关于查询数据的大小,如果查询的数据太小,直接遍历就可以,两者效率相差不大,如果要查找的数据太大,因为二分查找必须依赖顺序表结构,所以需要申请的空间必须是连续的,有可能会出现没有足够的连续内存空间的情况
实现:
数组arr:{1,4,7,8,12,43,56,87,98,323,3545,5685},利用二分查找返回数组下标
例:查找43输出5
public static int binary(int[] arr, int n){
int start = 0;
int end = arr.length - 1;
while (start<=end){
int mid = (start + end)/2;
if(arr[mid]== n){
return mid;
} else if (n > arr[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
递归实现:
public static int binary(int[] arr, int n, int start, int end){
if(start > end){
return -1;
}
int mid = (start + end)/2;
if(arr[mid] == n){
return mid;
} else if (n > arr[mid]) {
return binary(arr, n, mid + 1, end);
} else {
return binary(arr, n, start, mid - 1);
}
}
当数组中没有重复数据时,可以使用上述方法,但是有些需求可能是数组中有重复数据,需要查找数组中某个数的第一次出现的下标
例:数组{1,4,7,43,43,43,56,87,98,323,3545,5685},查找43输出3
public static int binary(int[] arr, int n){
int start = 0;
int end = arr.length - 1;
while (start<=end){
int mid = (start + end)/2;
if(arr[mid] == n && mid>0 && arr[mid -1] != n ){
return mid;
} else if (n > arr[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}