Smallest Element in rotated sorted array
  • sortedarray
  • array
  • rotation
  • searching
  •   
  • Posted: 5 years ago
  • Edit
  • answers (1)
  • views (1320)

You are given a sorted array of integers which is also rotated. How will you find the smallest element in the array?


Posted Answers

When rotation is performed on a sorted array of integers, the first (for sorted in ascending order) / last (for sorted in descending order) element is no longer the smallest element on the rotated array.
In this case, we can use the concept of binary search to find the smallest element.


  • If the middle element of the array is greater than the last element, search in the second half of the array.
  • Else, search in the first half of the array.

Running time = \( O(logn) \).

public static int FindMinInRotatedSortedArray(int[] array) {

/* Initialization */
int low = 0;
int high = array.length - 1;

while (array[low] > array[high]) {

int middle = (low + high) / 2;
if (array[middle] > array[high])
low = middle + 1;
else
high = middle;

}
return low;
}

You need to Sign In to post your solution.