Find element in sorted rotated array without finding pivot

Given a sorted integer array which is rotated any number of times and an integer num, find the index of num in the array. If not found, return -1.


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Algorithm/Insights

Use modified binary search to find the element
1. Initialize start = 0, end = array length - 1
2. Repeat following steps till start <= end:
3. Set mid = (start + end)/2          
4. If num == array[mid], return mid.
5. If array[start..mid] is sorted, i.e. array[start] < array[mid]
    a). If array[start] <= num <= array[mid], set end = mid-1
    b). Else set start = mid+1
6. Else If array[mid..end] is sorted, i.e. array[mid] < array[end]
    a). If array[mid] <= num <= array[end], set start = mid+1
    b). Else set end = mid-1
7. If not found, return -1.


Algorithm Visualization




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 a sorted rotated array without finding pivot<br>
 * Given a sorted integer array which is rotated any number of times and an integer num, find the index of num in the array. 
 * If not found, return -1.
 * 
 * Example: <br>
 * array = { 56, 58, 67, 76, 21, 32, 37, 40, 45, 49 }
 * <br>
 * integer = 45
 * <br>
 * Output: 8
 * <br><br>
 * <a href="https://www.youtube.com/watch?v=PWFCbWt7VwY">Find element in sorted rotated array Youtube Link</a> 
 * @author Saurabh
 *
 */
public class FindElementSortedRotatedArrayWithoutPivot {
	
	// Find an element in a sorted rotated array without finding pivot
	public static int findElementUsingBinarySearch(int[] array, int num) {
		if(array == null || array.length == 0) {
			return -1;
		}
		
		int start = 0;
		int end = array.length-1;
		
		while(start <= end) {
			
			int mid = (start + end)/2;
			if(num == array[mid]) {
				return mid;
			} 
			
			if(array[start] <= array[mid]) {  // array[start...mid] is sorted

				if(array[start] <= num && num <= array[mid]) { // num lies between array[start...mid]
					end = mid-1;
				} else {
					start = mid+1;
				}
			} else {   // array[mid...end] is sorted
				
				if(array[mid] <= num && num <= array[end]) { // num lies between array[mid...end]
					start = mid+1;
				} else {
					end = mid-1;
				}
			}
		}
		
		return -1;
	}
	
	public static void main(String[] args) {
		{
			int array[] = { 56, 58, 67, 76, 21, 32, 37, 40, 45, 49 };
			findElementUsingBinarySearchTest(array, 45);
		}
	}

	private static void findElementUsingBinarySearchTest(int[] array, int num) {
		System.out.println("Element " + num + " found at = " + findElementUsingBinarySearch(array, num));
	}

}
		

Order of the Algorithm

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


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.


    Saurabh Kumar