CODEWITHSUNDEEP
javac++algorithmdata-structuresbinary-search
Boolean
Boolean

Reputation: 14664

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

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??

Upvotes: 17

Views: 13641

Answers (11)

ak_05
ak_05

Reputation: 21

In C++, one can use this code ( O(log(n)) ) to get the number of rotations in a rotated sorted list:

findRotations(const vector<int> &A) {
    int len = A.size(), low = 0, high = len - 1, result = -1, target = A[len-1];

    while(low <= high){
        int  mid = low + (high-low)/2;
        if(A[mid] > target){
            low = mid + 1;
        }
        else{
            result = mid;
            high = mid - 1;
        }
    }

    return result;
}

In case the list is not sorted, you should know what the array was originally and you can check linearly for the point of rotation ( O(n) ).

Upvotes: 2

sakra
sakra

Reputation: 65971

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

Upvotes: 2

user1710310
user1710310

Reputation: 21

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

Upvotes: 2

HitOdessit
HitOdessit

Reputation: 7266

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.

Upvotes: 2

polygenelubricants
polygenelubricants

Reputation: 383966

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

Upvotes: 29

tkr
tkr

Reputation: 1381

Here is a picture to illustrate the suggested algorithms:

alt text

Upvotes: 10

Potatoswatter
Potatoswatter

Reputation: 137910

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.

Upvotes: 2

kludg
kludg

Reputation: 27493

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;

Upvotes: 2

rlbond
rlbond

Reputation: 67839

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.

Upvotes: 3

Nikita Rybak
Nikita Rybak

Reputation: 68026

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

Upvotes: 3

Billy ONeal
Billy ONeal

Reputation: 106609

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

Upvotes: 1

Related Questions