java 二分法查询

时间:2021-06-15 22:10:48
/*
* 折半查找,二分查找:
* 前提:数组必须是有序的。
*/

public class ArrayDemo2 {
public static void main(String[] args) {
int[] arr = { 18, 37, 54, 76, 92 };

// 如何获取数据92在数组中的索引呢
//int index = getIndex(arr, 92);
int index = getIndex(arr, 76);
//int index = getIndex(arr, 26);
System.out.println(index);
}

public static int getIndex(int[] arr, int value) {
// 定义最大索引
int maxIndex = arr.length - 1;
// 定义最小索引
int minIndex = 0;
// 定义中间索引
int midIndex = (maxIndex + minIndex) / 2;

while (arr[midIndex] != value) {
if (arr[midIndex] > value) {
maxIndex = midIndex - 1;
} else if (arr[midIndex] < value) {
minIndex = midIndex + 1;
}

// 如果数据不存在。
if (minIndex > maxIndex) {
return -1;
}

// 下一次二分查找开始
midIndex = (maxIndex + minIndex) / 2;
}
return midIndex;
}
}