CareerCup

Modified Binary search will do

int search(int a[], int l, int u, int x) {
    while (l <= u) {
        int m = (l + u) / 2;
        if (x == a[m]) {
            return m;
        } else if (a[l] <= a[m]) {
            if (x > a[m]) {
                l = m+1;
            } else if (x >=a [l]) {
                u = m-1;
            } else {
                l = m+1;
            }
        }
        else if (x < a[m]) u = m-1;
        else if (x <= a[u]) l = m+1;
        else u = m - 1;
    }
    return -1;
}

Incomplete question.

Is it supposed to be a sorted array which has been rotated an unknown number of times?

binary search + shift

this question has som mistak i guess???

This is a cyclically ordered list. We can use a variant of binary search like cyclic binary search ( with little modification) to solve the problem.

This is a cyclically ordered list. We can use a variant of binary search like cyclic binary search ( with little modification) to solve the problem.

Approach:
1. First search for the index of the element which is inverted. Example in the example given array {5,6,7,8,9,10,1,2,3,4} the index is '5' (element 10). Running time (lg n) [Modified binary search]
2. Do an ordinary binary search in the appropriate sub-array.

/*
     * Return the index of the highest element in the array
     */
    public int searchForBoundry(int[] arr, int start, int end) {
    	if (start >= end) {
    		return -1;
    	}   	
    	int mid = start + (end-start)/2;
    	
    	if (arr[mid] > arr[mid+1]) {
    		return mid;
    	}
    	if (arr[start] < arr[mid]) {
    		return searchForBoundry(arr, mid, end);
    	} else {
    		return searchForBoundry(arr, start, mid);
    	}
    }
    
    /*
     * Ordinary Binary Search
     */
    public int binarySearch(int[] arr, int start, int end, int element) {
    	if (start > end) {
    		return -1;
    	}
    	
    	int mid = start + (end-start)/2;
    	
    	if (arr[mid] > element) {
    		return binarySearch(arr, start, mid-1, element);
    	} else if (arr[mid] < element) {
    		return binarySearch(arr, mid+1, end, element);    		
    	}else {
    		return mid;
    	}
    }
    
    public int searchCircular(int[] arr, int start, int end, int element) {
    	int index = searchForBoundry(arr, start, end);
    	if (index != -1) {
    		if (arr[start] > element) {
    			return binarySearch(arr, index+1, end, element);
    		} else {
    			return binarySearch(arr, start, index, element);
    		}
    	} else {
    		return -1;
    	}
    }