二分查找
二分查找必要条件有两个
- 必须是顺序存储结构
- 必须有序
算法思想
- 将给定的目标值target与中间位置值作比较，相等则查找成功
- 若是不相等则利用中间位置记录将表分为前后两个子表。如果target比中间位置值小，则下一次在前一子表继续查找；若target比中间位置值大，则下一次在后一子表继续查找。
- 重复上面两个操作，不断将查找区间进行对折，知道查找成功;或者查找区间为空，则查找失败。
代码如下
public class BinarySearch {
public static void main(String[] args) throws Exception {
int[] array = generateArray();
int target = 12;
printArray(array);
int result = binarySearch(array, target);
System.out.println(result == -1 ? "未查找到目标数据 : " + target : "查找到目标数据，在第" + result + "号元素");
}
private static int[] generateArray() {
int length = 10 + new Random().nextInt(20);
int[] array = new int[length];
for (int i = 0; i < array.length; i++) {
array[i] = 2 + 2 * i;
}
return array;
}
private static void printArray(int[] array) {
System.out.println("数组内容是：");
for (int i : array) {
System.out.print(i + "\t");
}
System.out.print("\n");
}
//二分查找代码部分
public static int binarySearch(int[] array, int target) {
int start = 0;
int end = array.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (target == array[mid]) {
return mid;
} else if (target < array[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
}
