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

15

12

I have a sorted list which is rotated and 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??

Boolean

Posted 2010-05-09T02:35:01.810

Reputation: 5 570

Am I the only one who, when reads "list" thinks about a data structure that doesn't support random access? – Maciej Hehl – 2010-05-10T02:40:46.120

@Maciej: even if you're not the only one, that's still a wrong conclusion to make. In Java, ArrayList<E> implements List<E>, RandomAccess. On the other hand, LinkedList<E> is not RandomAccess. – polygenelubricants – 2010-05-10T02:52:34.367

Just as I thought. The problem is with java :) Thx. – Maciej Hehl – 2010-05-10T02:55:49.367

Answers

24

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


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

polygenelubricants

Posted 2010-05-09T02:35:01.810

Reputation: 278 287

2+1 for mentioning the duplicates problem. – Ritsaert Hornstra – 2010-05-09T07:12:29.773

1-1 Do not steal code without references – kludg – 2010-05-09T07:48:37.763

@Serg: I've deleted my comments; politics and drama goes to meta (http://meta.stackexchange.com/questions/49383/downvoted-by-others-because-they-want-credit)

– polygenelubricants – 2010-05-10T03:39:20.743

Wouldn't it be more correct if you replace the line (low + high) &gt;&gt;&gt; 1; with (low + high - 1) &gt;&gt;&gt; 1 ? This discards candidates more quickly. Moreover, I tried to modify this code to find the greatest element and in that case (low + high + 1) &gt;&gt;&gt; 1 is the only correct choice. See my topic http://stackoverflow.com/questions/4844165/safe-integer-middle-value-formula for details.

– eold – 2011-02-23T14:13:59.150

@ polygenelubricants - IMHO, the idea of binary-search will work only if the sorted sequence is strictly increasing. For example, for the input { 2,3,3,4,4,2,2 }, the expected (assume clock-wise) rotation is 5 but the above code will tell us "Min is 2 at 0". May be you could explicitly mention the assumption. – KGhatak – 2016-11-09T18:51:30.373

8

Here is a picture to illustrate the suggested algorithms:

alt text

tkr

Posted 2010-05-09T02:35:01.810

Reputation: 971

This was very helpful. Thank you @tjr. – Boolean – 2010-05-09T20:16:20.740

this is the best answer, "give a man a fish and you feed him for a day; teach a man to fish and you feed him for a lifetime" – Mhd.Tahawi – 2016-03-25T20:31:20.387

3

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

Nikita Rybak

Posted 2010-05-09T02:35:01.810

Reputation: 56 023

A direct binary search doesn't work because the list has been rotated. – Billy ONeal – 2010-05-09T03:09:43.530

Please note that binary search in its traditional form looks for particular value, not for minimum of the function. Thus, 'traditional conditions' can't be applied too. Anyway, I added comment in the code to explain the logic. – Nikita Rybak – 2010-05-09T03:16:13.127

@Billy ONeal And looks like you posted the same algorithm :) – Nikita Rybak – 2010-05-09T03:19:48.297

3

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.

rlbond

Posted 2010-05-09T02:35:01.810

Reputation: 38 152

2

Recursion is very good if we want to maintain simplicity and readability of the code. But if we can avoid recursion and still maintain the readability, it would be better because recursion cost is significant and not actually scalable.

Here is a simple iterative method with logic pretty much as discussed above ( it's taking advantage of binary search, adding small partition logic).

private static int partitionSearch(int[] sortedArray, int numToFind) {
    if(sortedArray[0] > numToFind && sortedArray[sortedArray.length -1 ] < numToFind)
        return -1;
    boolean isInFirstPartition = sortedArray[0] <= numToFind;

    int startIndex = 0;
    int endIndex = sortedArray.length -1;
    int currentIndex;
    int currentValue;
    if(isInFirstPartition) { 
        do {
            currentIndex = (startIndex + endIndex) / 2;
            currentValue = sortedArray[currentIndex];
            if(currentValue == numToFind)
                return currentIndex;
            if(currentValue > sortedArray[startIndex] && sortedArray[currentIndex] < numToFind)
                startIndex = currentIndex + 1;
            else
                endIndex = currentIndex - 1;
        } while (startIndex <= endIndex);
    } else {
        do {
            currentIndex = (startIndex + endIndex) / 2;
            currentValue = sortedArray[currentIndex];
            if(currentValue == numToFind)
                return currentIndex;
            if(currentValue < sortedArray[endIndex] && sortedArray[currentIndex] > numToFind)
                endIndex = currentIndex - 1;
            else
                startIndex = currentIndex + 1;
        } while (startIndex <= endIndex);
    }
    return -1;
}

user1710310

Posted 2010-05-09T02:35:01.810

Reputation: 21

1'... if we can avoid it and still maintain the readability it should be good' This has no basis what so ever – raam86 – 2012-09-30T23:08:37.683

2

My version of binary search algorithm implementation in Java:

/**
 * Works only for arrays with NO duplicates.
 * Work also for zero-shifted array, e.g fully sorted, when shift = 0.
 */
public static int searchInShiftedArr(int[] arr, int key) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int low = 0;
    int high = arr.length - 1;
    int mid; // declared outside loop to avoid constant memory allocation for this variable
    while (low <= high) {
        mid = (low + high) >>> 1; // same as "(low + high) / 2", but avoid negative overflow and should be faster than "low + (high - low)/2"
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[low] <= arr[mid]) { // means left half of the array is sorted
            if (arr[low] <= key && key < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        } else { // means right half of the array is sorted
            if (arr[mid] < key && key <= arr[high]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return -1;
}

Code successfully passed 5000 TestCases, so I think it's production ready.

HitOdessit

Posted 2010-05-09T02:35:01.810

Reputation: 6 268

2

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.

Potatoswatter

Posted 2010-05-09T02:35:01.810

Reputation: 108 946

2

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;

kludg

Posted 2010-05-09T02:35:01.810

Reputation: 24 037

1

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;
}

Billy ONeal

Posted 2010-05-09T02:35:01.810

Reputation: 71 427

1

In C++ 11, this problem can be solved with partition_point:

std::vector<int> arr = {5,6,7,8,1,2,3,4};
auto rotation_point = std::partition_point(arr.begin(), std::prev(arr.end()),
    [&arr](int elem) { return elem > arr.back(); });

sakra

Posted 2010-05-09T02:35:01.810

Reputation: 38 226