Binary search to find the rotation point in a rotated sorted list

Question

I am having a sorted list which is rotated and I would like to do a binary search on that list to find the minimum element.

Lets suppose initial list is {1,2,3,4,5,6,7,8} rotated list can be like {5,6,7,8,1,2,3,4}

Normal binary search doesn't work in this case. Any idea how to do this.

-- Edit

I have one another condition. What if the list is not sorted??

Answer 1

I would like to do a binary search on that list to find the minimum element.
Ternary search will work for such case: when function has exactly one local minimum.

http://en.wikipedia.org/wiki/Ternary_search

edit Upon second reading, I probably misunderstood the question: function does not conform requirements for ternary search :/ But won't binary search work? Suppose, original order was increasing.

if (f(left) < f(middle)) 
    // which means, 'left' and 'middle' are on the same segment (before or after point X we search)
    // and also 'left' is before X by definition
    // so, X must be to the right from 'middle'
    left = middle
else
    right = middle

Answer 2

Something like this might work (Not tested):

//assumes the list is a std::vector<int> myList

int FindMinFromRotated(std::vector<int>::iterator begin, std::vector<int>::iterator end) {
    if (begin == end)
        throw std::invalid_argument("Iterator range is singular!");
    if (std::distance(begin, end) == 1) //What's the min of one element?
        return *begin;
    if (*begin < *end) //List is sorted if this is true.
        return *begin;
    std::vector<int>::iterator middle(begin);
    std::advance(middle, std::distance(begin, end)/2);
    if (*middle < *begin) //If this is true, than the middle element selected is past the rotation point
        return FindMinFromRotated(begin, middle)
    else if (*middle > *begin) //If this is true, the the middle element selected is in front of the rotation point.
        return FindMinFromRotated(middle, end)
    else //Looks like we found what we need :)
        return *begin;
}

Answer 3

A slight modification on the binary search algorithm is all you need; here's the solution in complete runnable Java (see Serg's answer for Delphi implementation, and tkr's answer for visual explanation of the algorithm).

import java.util.*;
public class BinarySearch {
    static int findMinimum(Integer[] arr) {
        int low = 0;
        int high = arr.length - 1;
        while (arr[low] > arr[high]) {
            int mid = (low + high) >>> 1;
            if (arr[mid] > arr[high]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
    public static void main(String[] args) {
        Integer[] arr = { 1, 2, 3, 4, 5, 6, 7 };
        // must be in sorted order, allowing rotation, and contain no duplicates

        for (int i = 0; i < arr.length; i++) {
            System.out.print(Arrays.toString(arr));
            int minIndex = findMinimum(arr);
            System.out.println(" Min is " + arr[minIndex] + " at " + minIndex);
            Collections.rotate(Arrays.asList(arr), 1);
        }
    }
}

This prints:

[1, 2, 3, 4, 5, 6, 7] Min is 1 at 0
[7, 1, 2, 3, 4, 5, 6] Min is 1 at 1
[6, 7, 1, 2, 3, 4, 5] Min is 1 at 2
[5, 6, 7, 1, 2, 3, 4] Min is 1 at 3
[4, 5, 6, 7, 1, 2, 3] Min is 1 at 4
[3, 4, 5, 6, 7, 1, 2] Min is 1 at 5
[2, 3, 4, 5, 6, 7, 1] Min is 1 at 6

See also

• Java Collections.rotate() with an array doesn’t work
  • Explains why Integer[] instead of int[]
• Google Research Blog: Nearly All Binary Searches and Mergesorts are Broken
  • Explains why >>> 1 instead of / 2

---

On duplicates

Note that duplicates makes it impossible to do this in O(log N). Consider the following bit array consisting of many 1, and one 0:

  (sorted)
  01111111111111111111111111111111111111111111111111111111111111111
  ^

  (rotated)
  11111111111111111111111111111111111111111111101111111111111111111
                                               ^

  (rotated)
  11111111111111101111111111111111111111111111111111111111111111111
                 ^

This array can be rotated in N ways, and locating the 0 in O(log N) is impossible, since there's no way to tell if it's in the left or right side of the "middle".

---

I have one another condition. What if the list is not sorted??

Then, unless you want to sort it first and proceed from there, you'll have to do a linear search to find the minimum.

See also

• Wikipedia | Selection algorithm | Linear minimum/maximum algorithms

Answer 4

Pick some subsequence [i,j] of the list [first, last). Either [i,j] does not contain the discontinuity, in which case *i <= *j, or it does, in which case the remaining elements (j, last) U [first, i), are properly sorted, in which case *j <= *i.

Recursively bipartition the suspect range until you winnow down to one element. Takes O(log N) comparisons.

Answer 5

Delphi version - third improved (thanks to polygenelubricants code - yet one more comparison removed) variant:

type
  TIntegerArray = array of Integer;

function MinSearch(A: TIntegerArray): Integer;
var
  I, L, H: Integer;

begin
  L:= Low(A);   // = 0
  H:= High(A);  // = Length(A) - 1
  while A[L] > A[H] do begin
    I:= (L + H) div 2; // or (L + H) shr 1 to optimize
    Assert(I < H);
    if (A[I] > A[H])
      then L:= I + 1
      else H:= I;
  end;
  Result:= A[L];
end;

Answer 6

Just perform the bisection method on list - list[end] over the range [1, end). The bisection method looks for zeros in a function by searching for a sign change, and operates in O(log n).

For example,

{5,6,7,8,1,2,3,4} -> {1,2,3,4,-3,-2,-1,0}

Then use the (discretized) bisection method on that list {1,2,3,4,-3,-2,-1}. It will find a zero crossing between 4 and -3, which corresponds to your rotation point.

Answer 7

Here is a picture to illustrate the suggested algorithms: