二分查找数组中的转折点

有一个有序的数组，将其中的元素都右移X位，这样将该数组变成了一个部分有序的数组。位置0到X以及X+1到n-1是有序的，但是array[X] > array[X+1]。array[X+1]为原先数组的最小值，我们称其为转折点。请找出该X+1。

 

解题思路：使用二分查找的方法来搜索X+1，时间复杂度为O(logn)。考虑只有一个元素和数组仍然保持有序的特殊情况。

 

public class BinarySearch {
	
	private int[] array;
	
	public int search(int t) {
		int start = 0;
		int end = array.length - 1;
		int mid;
		
		while (start <= end) {
			mid = (start + end) / 2;
			if (array[mid] == t) {
				return mid;
			} else if (array[start] == t) {
				return start;
			} else if (array[mid] > t) {
				if (array[start] < array[mid]) {
					if (t < array[start])
						start = mid + 1;
					else
						end = mid - 1;
				} else {
					end = mid - 1;
				}
			} else {
				if (array[start] > array[mid]) {
					if (t < array[start])
						start = mid + 1;
					else
						end = mid - 1;
				} else {
					start = mid + 1;
				} 
			}
		}
		return -1;
	}
	
	public int find() {
		int start = 0;
		int end = array.length - 1;
		int mid;
		
		if (array[start] <= array[end])
			return 0;
		
		while (start <= end) {
			mid = (start + end) / 2;
			if (array[mid] > array[mid+1])
				return mid+1;
			else if (array[start] <= array[mid])
				start = mid + 1;
			else
				end = mid - 1;
		}
		return 0;
	}
	
	public static void main(String[] args) {
		BinarySearch bs = new BinarySearch();
		bs.array = new int[] {5,6,1,2,3,4};
		System.out.println(bs.find());
		System.out.println(bs.search(4));
	}
}

 

    对于部分有序数组的查找，也可以使用二分查找的思想，再稍加修改一些判断条件即可。