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

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.367Just as I thought. The problem is with java :) Thx. – Maciej Hehl – 2010-05-10T02:55:49.367