输入的数组前提是有序数组
面试得知下标索引容易越界，写出来可以，写对却不容易
public class binarySearch {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 6, 7, 8, 10, 11, 12};
// System.out.println(binarySearchtest(arr, 0, arr.length - 1, 77));
System.out.println(binarySearch(arr, 6));
}
//给定的数组前提是有序数组
static int binarySearchtest(int a[], int left, int right, int value) {
int middle = (left + right) /2;
int midVal = a[middle];
if (value < a[left] || value > a[right] || left > right) {
return -1;
}
if (midVal < value) {
return binarySearchtest(a, middle+1, right, value);
}else if (midVal > value) {
return binarySearchtest(a, left, middle-1, value);
}else {
return middle;
}
}
static int binarySearch(int a[], int value) {
int min =0;
int max = a.length -1;
while (min <= max) {
int mid = (min + max) /2;
int midVal = a[mid];
if (value == midVal) {
return mid;
}else if (value > midVal) {
min = mid +1;
}else {
max = mid -1;
}
}
return -1;
}
}
网友评论