Hi,

Today we will learn something about binary search. Not about original algorithm but about some interesting modification. I am talking about **Find Minimum in Rotated Sorted Array** from leetcode.

So, task description:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e.,

`0 1 2 4 5 6 7`

might become`4 5 6 7 0 1 2`

).Find the minimum element.

You may assume no duplicate exists in the array.

OK, lets go to thinking about the problem.

*What do we have ?*

We have sorted array with some rotation.

*What does rotation mean ? *

Rotation is like breaking array to two parts and concat from other side (like in example , input 0 1 2 4 5 6 7, broken to 0 1 2 and 4 5 6 7 and concat to result 4 5 6 7 0 1 2).

*OK, if this is sorted array we can use binary search to find needed element, is not it?*

Yes, we can but we have no input element, we have to find min in input array.

Hmm, interesting …

When I look at the example array 4 5 6 7 0 1 2 I noticed the movement of my eyes. If I look to the start of array my eyes moved to right (I am comparing with end element and see that end is smaller than start) if to the end – to left, if to the middle it depends what element I can see, to left or to right. So, I can try implement this behavior …

OK, we have two borders: start(**l**) and end(**r**) and can start usual iterative binary search.

while (l < r) {

After that calculate middle index like in binary search

int m = l + (r - l) / 2;

After that implementation of eyes behavior. If element I am looking for bigger than right one, go to the right, no, go to the left.

if (A[m] > A[r]) { l = m + 1; } else { r = m; }

OK, after that just return element from **l** or **r** indexes(in my solution **l**, but you can try **r**)

return A[l];

OK, that is all, try to test our solution using example array {4 5 6 7 0 1 2}:

**Step one:** l==0, r==6, m ==3, A[m] ==7, A[r] ==2

7 >2, so, l =m+1==4;

**Step two:** l==4, r==6, m ==5, A[m] ==1, A[r] ==2

1 < 2, so, r = 5;

**Step three:** l==4, r==5, m ==4, A[m] ==0, A[r] ==1

0 <1, so, r=4

**Step four:** l==4 and r==4 (while condition is false), break loop and get element from l or r index.

Cool, working :) You can try it on leetcode to check on more test cases.

Thanks.

Full code:

public int findMin(int[] num) { if (num.length == 0) return 0; return findMin(num, 0, num.length - 1); } int findMin(int[] A, int l, int r) { while (l < r) { int m = l + (r - l) / 2; if (A[m] > A[r]) { l = m + 1; } else { r = m; } } return A[l]; }