今天偶遇一朋友，听说沃老师当年学的CS专业，遂问沃老师二分查找算法的细节，而沃老师平常是不刷题的，有一个细节因为时间太久记不得了，遂被取笑，沃老师很生气，决定每日写一个算法的java实现一雪前耻，就以这个二分查找开始！
先说下思路
找到目标数组的中间点的数据pivot，然后跟目标值target进行比较，如果target小于pivot，那么可知target应在pivot的左侧，否则右边。这里我们假设在左边，那么只需对左侧的子数组进行递归操作即可；
public class Test {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 9, 12, 13};
System.out.println(binarySearch(arr, 0, 3));
System.out.println(binarySearch(arr, 0, 9));
System.out.println(binarySearch(arr, 0, 15));
}
@Nonnull
public static int binarySearch(@Nonnull int[] arr, int lowIndex, int target) {
int midIndex = arr.length / 2;
if (arr[midIndex] == target) {
return lowIndex + midIndex;
} else {
if (arr.length == 1) {
return -1;
} else {
int[] tempArr;
if (target > arr[midIndex]) {
tempArr = ArrayUtils.subarray(arr, midIndex, arr.length);
lowIndex = midIndex;
} else {
tempArr = ArrayUtils.subarray(arr, 0, midIndex);
lowIndex = 0;
}
return binarySearch(tempArr, lowIndex, target);
}
}
}
}
执行结果如下：
2
7
-1
