Leetcode problem: Search in a rotated array (classic problem)

Leetcode: Search In A Sorted Array.md

Leetcode: Search In A Sorted Array

This is a classic binary search problem, which I always struggle to get after not looking at it for some time.

There are many ways to accomplish, I will present 5 ways:

1. The standard way without knowledge of abstract binary search theory (both iterative and recursive)
2. Evaluation the following predicate: p(x): A[x] >= target
3. Evaluation of the following predicate: p(x): A[x] > target
4. Evaluation of the following predicate: p(x): A[x] < target
5. Evaluation of the following predicate: p(x): A[x] <= target

rotated_array_search.cpp

/*
 * Standard Solution: Recursive
 *
 * This is a classic problem! It adapts the binary search technique. Its time is O(logn). 
 * When one performs normal binary search, we make a decision to either go left or right
 * in the array depending on the value of the mid point chosen. When the array is rotated,
 * we cannot do this immediately. We first need to check two cases.
 *
 * Assume we want to go forwards (because midpoint is smaller than target)
 * if the last element in the array is less than the target element and
 * the first element is greater than the midpoint, then we must go backwards
 *
 * The symmetrical case applies to when we want to go backwards
 *
 * Time complexity: O(logn), space O(1)
 */

/*

class Solution {
public:
    int searchRotatedArray(int A[], int n, int target) {
        if (n==0) {
            throw -1;
        }
        
        int half = (n-1) / 2,
            first = A[0],
            last = A[n-1];
        
        if (A[half] < target) { //we want to go forward
            if (last < target && A[half] < first) { 
                //we must go backwards
                return searchRotatedArray(A, half, target);
            }
            
            return half+1+searchRotatedArray(A+half+1, n-half-1, target);
            
        }
        
        if (A[half] > target) { //we want to go backwards
            if (first > target && A[half] > last) { 
                //we must go forwards
                return half+1+searchRotatedArray(A+half+1, n-half-1, target);
            }
            
            return searchRotatedArray(A, half, target);
        }
        
        return half;
    }

    int search(int A[], int n, int target) {
        int index = 0;
        try {
            index = searchRotatedArray(A, n, target);
        } catch (int err) {
            index = -1;
        }
        
        return index;
    }
};

solution-iterative-predicate_function_1.cpp

class Solution {
public:
    /*
     * Predicate function: p(x): A[x] >= target
     * Goal: return first true
     */
    bool p(const int* A, int lo, int hi, int x, int target) {

        if (A[x] >= target) {
                if (A[x] > A[hi] && target <= A[hi]) return false;
                return true;
        }

        if (A[x] < target) {
                if (A[x] < A[lo] && A[lo] <= target) return true;

                return false;
        }
    }
    
    int search(int A[], int n, int target) {
        int hi=n-1, lo=0, mid=0;
        
        while (lo < hi) {
            mid = lo + (hi-lo) / 2;
            
            if (p(A, lo, hi, mid, target))
                hi = mid;
            else
                lo = mid+1;
        }
        
        if (A[lo] == target) return lo;
        
        return -1;
    }
};

solution-iterative-predicate_function_2.cpp

class Solution {
public:
    /*
     * Predicate function: p(x): A[x] > target
     * Goal: return last false
     */
    bool p(const int* A, int lo, int hi, int x, int target) {

        if (A[x] > target) {
                if (A[x] > A[hi] && target <= A[hi]) return false;
                return true;
        }

        if (A[x] <= target) {
                if (A[x] < A[lo] && A[lo] <= target) return true;

                return false;
        }
    }
    
    int search(int A[], int n, int target) {
        int hi=n-1, lo=0, mid=0;
        
        while (lo < hi) {
            mid = lo + (hi-lo+1) / 2;
            
            if (p(A, lo, hi, mid, target))
                hi = mid-1;
            else
                lo = mid;
        }
        
        if (A[lo] == target) return lo;
        
        return -1;
    }
};

solution-iterative-predicate_function_3.cpp

class Solution {
public:
    /*
     * Predicate function: p(x): A[x] < target
     * Goal: return first false
     */
    bool p(const int* A, int lo, int hi, int x, int target) {

        if (A[x] < target) {
                if (A[x] < A[lo] && A[lo] <= target) return false;
                return true;
        }

        if (A[x] >= target) {
                if (A[x] > A[hi] && target <= A[hi]) return true;

                return false;
        }
    }
    
    int search(int A[], int n, int target) {
        int hi=n-1, lo=0, mid=0;
        
        while (lo < hi) {
            mid = lo + (hi-lo) / 2;
            
            if (p(A, lo, hi, mid, target))
                lo = mid+1;
            else
                hi = mid;
        }
        
        if (A[lo] == target) return lo;
        
        return -1;
    }
};

solution-iterative-predicate_function_4.cpp

class Solution {
public:
    /*
     * Predicate function: p(x): A[x] <= target
     * Goal: return first true
     */
    bool p(const int* A, int lo, int hi, int x, int target) {

        if (A[x] <= target) {
                if (A[x] < A[lo] && A[lo] <= target) return false;
                return true;
        }

        if (A[x] > target) {
                if (A[x] > A[hi] && target <= A[hi]) return true;

                return false;
        }
    }
    
    int search(int A[], int n, int target) {
        int hi=n-1, lo=0, mid=0;
        
        while (lo < hi) {
            mid = lo + (hi-lo+1) / 2;
            
            if (p(A, lo, hi, mid, target))
                lo = mid;
            else
                hi = mid-1;
        }
        
        if (A[lo] == target) return lo;
        
        return -1;
    }
};

solution-iterative.cpp

/*
 * Standard Solution: Iterative
 */

class Solution {
public:
    int search(int A[], int n, int target) {
        int hi=n-1, lo=0, mid=0;
        
        while (lo < hi) {
            mid = lo + (hi-lo) / 2;
            if (A[mid] == target) return mid;
            
            if (A[mid] > target) {
                if (A[mid] > A[hi] && target <= A[hi]) lo = mid+1;
                else hi = mid-1;
            }
            
            if (A[mid] < target) {
                if (A[mid] < A[lo] && target >= A[lo]) hi = mid-1;
                else lo = mid+1;
            }
        }
        
        if (A[lo] == target) return lo;
        
        return -1;
    }
};