Magic index

find the index with value equal to index. Time Complexity: O(logn), Space Complexity: O(1).

	//numbers are distinct
	public int getMagic(int[] a, int start, int end) {
		if(start > end) return -1;
		int middle = start + (end - start) / 2;
		if(a[middle] == middle) return middle;
		else if(a[middle] > middle) return getMagic(a, start, middle - 1);
		else return getMagic(a, middle + 1, end);
	}
	
	//if numbers are not distinct, means have repeated numbers
	public int getMagic2(int[] a, int start, int end) {
		if(start > end) return -1;
		int middle = start + (end - start) / 2;
		if(a[middle] == middle) return middle;
		
		//search left
		//the min leftIndex should be compare with the value 
		int leftIndex = Math.min(middle - 1, a[middle]);
		int left = getMagic2(a, start, leftIndex);
		if(left >= 0) return left;
		
		//search right 
		int rightIndex = Math.max(middle + 1, a[middle]);
		int right = getMagic2(a, rightIndex, end);
		return right;
	}