Find an element in a sorted rotated array

Algorithm/Insights

Linear Search:
    Given an integer array 'array' and an integer 'num'.
        1. If array is null or is of 0 length, return -1.
        2. Start with index = 0.
        3. Check if array[index] == num, then return index.
        4. Otherwise index++.
        5. Repeat steps 3 and 4 till index < array length.
        6. If not found, return -1.
    Time Complexity: O(n)
    Space Complexity: O(1)

Using Binary Search:
    Step 1: Find index of pivot element (minimum element)
    Step 2: Apply Binary Search on the subarray based on following conditions:
        1. If num lies between start element and element at pivot-1 position, then find num in array[start..pivot-1] using binary search
        2. Else if num lies between pivot and last element, then find num in array[pivot..end] using binary search
    
    Algorithm for finding index of pivot element:
    1. If array[0] <= array[length of array - 1], it means the array is not rotated, so return 0.
    2. Initialize start = 0, end = length of array - 1.
    3. Repeat following steps till start <= end
       a). Set mid = (start+end)/2.
       b). If mid+1 is pivot, then break.
       c). If array[start] <= array[mid], it means from start to mid, all elements are in sorted order. Set start = mid+1, so that we look for pivot in second half of the array.
       d). Else set end = mid-1, to look for pivot in first half.
    
    Binary Search algorithm:
    Start and end are passed as parameter.
    1. Repeat following steps till start <= end:  
    2. Set mid = (start + end)/2.
    3. Check if array[mid] == num, then return mid.
    4. If num < array[mid], set end = mid-1.
    5. Else set start = mid+1.
    6. Return -1.

Code Snippet

			
package com.ideserve.saurabh.questions;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * <br><br>
 * Find an element in sorted rotated array</b><br>
 * Given a sorted rotated integer array and an integer, find the index of the integer in the array. If not found, return -1.
 * 
 * Example: <br>
 * array = { 97, 108, 149, 21, 32, 43, 74, 75, 86 }
 * <br>
 * integer = 43
 * <br>
 * Output: 5
 * <br><br>
 * <a href="https://www.youtube.com/watch?v=6pSzsJH56BA">Find an element in a sorted rotated array Youtube Link</a> 
 * @author Saurabh
 *
 */
public class FindElementSortedRotatedArray {
	
	public static int findElementInSortedRotatedArray(int array[], int num) {

		if (array == null || array.length == 0) {
			return -1;
		}

		int pivot = findPivot(array);

		if (pivot > 0 && num >= array[0] && num <= array[pivot - 1]) {
			return binarySearch(array, 0, pivot - 1, num);
		} else {
			return binarySearch(array, pivot, array.length - 1, num);
		}
	}
	
	public static int findPivot(int[] array) {

		if (array == null || array.length == 0) {
			return -1;
		}

		if (array.length == 1 || array[0] < array[array.length - 1]) {
			return 0;
		}

		int start = 0, end = array.length - 1;

		while (start <= end) {

			int mid = (start + end) / 2;
			// check if mid+1 is pivot
			if ( array[mid] > array[mid + 1]) {
				return mid + 1;
			} else if (array[start] <= array[mid]) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}

		return 0;
	}
	
	public static int binarySearch(int[] array, int start, int end, int num) {
		
		if (array == null || array.length == 0) {
			return -1;
		}
		
		if(start > end || start < 0 || end >= array.length) {
			throw new IllegalArgumentException("Invalid values for start and end! start = " + start + ", end = " + end);
		}

		if(num < array[start] || num > array[end]) {
			return -1;
		}
		
		while (start <= end) {

			int mid = (start + end) / 2;
			if (array[mid] == num) {
				return mid;
			} else if (num < array[mid]) {
				end = mid - 1;
			} else {
				start = mid + 1;
			}
		}

		return -1;
	}
	
	public static void main(String[] args) {
			int array[] = { 156, 235, 457, 21, 32, 43, 74, 75, 86, 97, 108, 149 };
			findElementInSortedRotatedArrayTest(array, 43);
	}

	private static void findElementInSortedRotatedArrayTest(int[] array, int num) {		
		int index = findElementInSortedRotatedArray(array, num);
		System.out.println("Element " + num + (index >= 0 ? (" found at index " + index) : " not found!"));
	}

}
		

Order of the Algorithm

Time Complexity is O(log n)
Space Complexity is O(1)