Min element in an array

A sorted array has been rotated so that the elements might appear in the order 3 4 5 6 7 1 2. How would you find the minimum element?

Finding the minimum element in an array isn’t a particularly interesting algorithm (you could just iterate through all the elements), nor does it use the information provided (that the array is sorted). It’s unlikely to be useful here.
However, binary search is very applicable. You know that the array is sorted, but rotated. So, it must proceed in an increasing order, then reset and increase again. The minimum element is the “reset” point.

If you compare the first and middle element (3 and 6), you know that the range is still increasing. This means that the reset point must be after the 6 (or, 3 is the minimum element and the array was never rotated). We can continue to apply the lessons from binary search to pinpoint this reset point, by looking for ranges where LEFT > RIGHT. That is, for a particular point, if LEFT < RIGHT, then the range does not contain the reset. If LEFT > RIGHT, then it does.

public class GetMinElement {
 public static void main(String[] args) {
  int[] a = { 3, 4, 5, 6, 2 };
  int pos = getMinimumElementInRotatedArray(a, 0, a.length - 1);
  System.out.println(a[pos]);
 }

 private static int getMinimumElementInRotatedArray(int[] a, int first,
   int last) {
  int mid;
  while (first < last) {
   mid = (first + last) / 2;
   if (a[mid] > a[last]) {
    first = mid + 1;
   } else {
    last = mid;
   }
  }
  return first;
 }
}