SYSTEM
查找
src/content/notes/system/查找.md 查找
正常查找:从第一个元素开始遍历,一个一个的往后找,综合查找比较耗时
二分查找也称折半查找(Binary Search)是一种效率较高的查找方法,数组必须是有序数组
过程:每次先与中间的元素进行比较,如果大于往右边找,如果小于往左边找,如果等于就返回该元素索引位置,如果没有该元素,返回 -1
时间复杂度:O(logn)
/*定义一个方法,记录开始的索引位置和结束的索引位置。
取出中间索引位置的值,拿元素与中间位置的值进行比较,如果小于中间值,结束位置=中间索引-1.
取出中间索引位置的值,拿元素与中间位置的值进行比较,如果大于中间值,开始位置=中间索引+1.
循环正常执行的条件:开始位置索引<=结束位置索引。否则说明寻找完毕但是没有该元素值返回-1.*/
public class binarySearch {
public static void main(String[] args) {
int[] arr = {10, 14, 21, 38, 45, 47, 53, 81, 87, 99};
System.out.println("81的索引是:" + binarySearch(arr,81));
}
public static int binarySearch(int[] arr, int des) {
int start = 0;
int end = arr.length - 1;
// 确保不会出现重复查找,越界
while (start <= end) {
// 计算出中间索引值
int mid = (start + end) / 2;
if (des == arr[mid]) {
return mid;
} else if (des > arr[mid]) {
start = mid + 1;
} else if (des < arr[mid]) {
end = mid - 1;
}
}
// 如果上述循环执行完毕还没有返回索引,说明根本不存在该元素值,直接返回-1
return -1;
}
}

查找第一个匹配的元素:
public static int binarySearch(int[] arr, int des) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (des == arr[mid]) {
//如果 mid 等于 0,那这个元素已经是数组的第一个元素,那肯定是我要找的
if (mid == 0 || a[mid - 1] != des) {
return mid;
} else {
//a[mid]前面的一个元素 a[mid-1]也等于 value,
//要找的元素肯定出现在[low, mid-1]之间
high = mid - 1
}
} else if (des > arr[mid]) {
start = mid + 1;
} else if (des < arr[mid]) {
end = mid - 1;
}
}
return -1;
}