gistfile1.txt

public static int search(int[] arr, int leftIndex, int rightIndex, int x){
		int mid = (leftIndex+rightIndex)/2;
		if(arr[mid] == x){
			return arr[mid];
		}
		if(rightIndex < leftIndex){
			return -1;
		}
		
		if(arr[mid] > arr[leftIndex]){
			//case 1: left is normal
			if(x <= arr[mid] && x >= arr[leftIndex]){
				return search(arr, leftIndex, mid-1, x);
			}else{
				return search(arr, mid+1, rightIndex, x);
			}
		}else if(arr[mid] < arr[leftIndex]){
			//case 2: right is normal
			if(x >= arr[mid] && x <= arr[rightIndex]){
				return search(arr, mid+1, rightIndex, x);
			}else{
				return search(arr, leftIndex, mid-1, x);
			}
		}else if(arr[mid] == arr[leftIndex]){
			//duplicates on the left
			if(arr[mid] != arr[rightIndex]){ //no duplicates on the right
				return search(arr, mid+1, arr[rightIndex], x);
			}else{
				//the entirety of the arr is duplicates, since the above conditions constrain arr[leftIndex] == arr[mid] == arr[rightIndex]
				int s = search(arr, mid+1, arr[rightIndex], x);
				if(s == -1){
					return -1;
				}
				return s;
			}
		}else{
			return -1;
		}
	}