Rotated Array Binary Search: Given a sorted list of integers, an arbitrary split is made such that the end of the first list is appended to the first, i.e.: 1 2 3 4 5 6 7 8 becomes: 6 7 8 1 2 3 4 5 Find the index of a number N in the array, returning -1 if it does not exist.

RotatedBinarySearch.java

public int rotatedBinarySearch(int[] array, int n, int low, int high){
    if (low > high){
        return -1;
    }
    int mid = (low + high) / 2;
    if (array[mid] == n){
        return mid;
    }
    
    if (array[low] < array[mid]){
        //left is normally ordered
        if (n >= array[low] && n <= array[mid]){
            return rotatedBinarySearch(array, n, low, mid-1);
        }
        else{
            return rotatedBinarySearch(array, n, mid+1, high);
        }
        
    }
    else if (array[mid] < array[right]){
        //right is normally ordered
        if (n >= array[mid] && n <= array[high]){
            return rotatedBinarySearch(array, n, mid+1, high);
        }
        else{
            return rotatedBinarySearch(array, n, low, mid-1);
        }
    }
    
}


//Iterative solution:

public class Solution {
    public int search(int[] A, int target) {
        int left = 0;
        int right = A.length - 1;
        
        if (right == 0){
            if (A[0] == target) return 0;
            else return -1;
        }
        
        while (left < right){
            int mid = (left + right) / 2;
            if (A[mid] == target){
                return mid;
            }
            
            if (A[left] <= A[mid]){
                //left half sorted
                if (target >= A[left] && target <= A[mid]){
                    right = mid-1;
                }
                else{
                    left = mid+1;
                }
            }
            else if (A[mid] <= A[right]){
                //right half sorted
                if (target > A[mid] && target <= A[right]){
                    left = mid+1;
                }
                else{
                    right = mid-1;
                }
            }
        
        }
        
        if (A[left] == target) return left;
        
        return -1;
    }
}





//Variation, find minimum element in a rotated sorted array

public class Solution {
    public int findMin(int[] num) {

        int low = 0;
        int high = num.length - 1;
        
        while (low < high){
            
            if (num[low] < num[high]) return num[low];
            
            if (high == low + 1) return Math.min(num[low], num[high]);
            
            int mid = (low + high) / 2;
            
            if (mid > 0 && num[mid] < num[mid-1]){
                return num[mid];
            } 
        
            if (num[low] < num[mid]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
       return num[low];
    }
    
}