二分查找Java实现

1.问：一个有序数组，找出给定值的索引值
通过使用二分查找实现，时间复杂度为O(log2N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class BinarySearch {

	public static int binarySearch(int array[], int number, int value) {
		int left = 0;
		int right = number - 1;
		while (left <= right) {
			int middle = left + ((right - left) >> 1);
			if (array[middle] > value) {
				right = middle - 1;
			} else if (array[middle] < value) {
				left = middle + 1;
			} else {
				return middle;
			}
		}
		return -1;
	}
}

2.问:一个数组是由一个递减数列左移若干位形成的，例{4，5，6，1，2，3}，找出给定值的索引值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class BinarySearch {
	public static int binarySearch(int array[], int number, int value) {
		int left = 0;
		int right = number - 1;
		int mid;
		while(left <= right){
			mid = left + (right - left) / 2;
			if(array[mid] == value){
				return mid;
			}else {
				if(array[left] <= array[mid]){
					if(array[left] <= value && value < array[mid]){
						right = mid - 1;
					}else{
						left = mid + 1;
					}
				}else {
					if(array[mid] <= value && value < array[right]){
						left = mid + 1;
					}else{
						right = mid - 1;
					}
				}
			}
		}
		return -1;
	}
}