Java 二分法搜索数组
## 介绍
二分法充分利用了元素间的次序关系。
### 基本思想
将n个元素（假设元素呈升序排列）分成个数大致相同的两半，取a\[n/2\]与欲查找的x作比较。
如果x=a\[n/2\]，则找到x，算法终止。
如果x＜a\[n/2\]，则只要在数组a的左半部继续搜索x。
如果x＞a\[n/2\]，则只要在数组a的右半部继续搜索x。
### 局限性
必须是在有序的元素中进行的，不能在无序的元素中使用。
## 示例
### 递归方式搜索
```java
import java.util.Arrays;
public class BinarySearchTest {
public static int binarySearch(int[] array, int number, int startIndex, int endIndex) {
int middleIndex = (startIndex + endIndex) / 2;
// 判断要搜索的数字是否合理
if (startIndex > endIndex)
return -1;
if (number < array[middleIndex]) { // 搜索数字位于数组前半部分
return binarySearch(array, number, startIndex, middleIndex - 1);// 运用递归
} else if (number > array[middleIndex]) { // 搜索数字位于数组后半部分
return binarySearch(array, number, middleIndex + 1, endIndex);// 运用递归
} else if (number == array[middleIndex]) {
return middleIndex;
}
return -1;
}
public static void main(String[] args) {
int[] array = new int[] { 12, 3, 2, 18, 24, 15, 20 };
// 二分法搜索元素之前必须对数组进行排序
Arrays.sort(array);
// 要查找的值
int number = 18;
System.out.println("排序后的数组：" + Arrays.toString(array));
System.out.println("元素 " + number + " 所在的位置下标是：" + binarySearch(array, number, 0, array.length - 1));
number = 1;
System.out.println("元素 " + number + " 所在的位置下标是：" + binarySearch(array, number, 0, array.length - 1));
}
}
```
### 遍历方式搜索
```java
import java.util.Arrays;
public class BinarySearchTest {
public static int binarySearch(int[] array, int number) {
int beginIndex = 0;
int endIndex = array.length - 1;
// 循环判断，根据起始位置与结束位置是否相等
while (beginIndex <= endIndex) {
// 获得数组中间位置
int midIndex = (beginIndex + endIndex) / 2;
if (number < array[midIndex]) { // 搜索数字位于数组前半部分
// 重新定位结束位置
endIndex = midIndex - 1;
} else if (number > array[midIndex]) {// 搜索数字位于数组后半部分
// 重新定位起始位置
beginIndex = midIndex + 1;
} else {// 搜索数字位于数组中间
return midIndex;
}
}
return -1;
}
public static void main(String[] args) {
int[] array = new int[] { 12, 3, 2, 18, 24, 15, 20 };
// 二分法搜索元素之前必须对数组进行排序
Arrays.sort(array);
// 要查找的值
int number = 18;
System.out.println("排序后的数组：" + Arrays.toString(array));
System.out.println("元素 " + number + " 所在的位置下标是：" + binarySearch(array, number));
number = 1;
System.out.println("元素 " + number + " 所在的位置下标是：" + binarySearch(array, number));
}
}
```
## 二分法模板
```java
public static int bisectionSearch(int[] arr, int key) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int middle = (start + end) / 2;
if (key < arr[middle]) {
end = middle - 1;
} else if (key > arr[middle]) {
start = middle + 1;
} else {
return middle;
}
}
return -1;
}
```