# Binary Search Solution in Java

• Hi:
This is my accepted solution, which uses binary search. O(logN).

``````public int findMin(int[] num) {
int low = 0;
int high = num.length - 1;
if (num[low] < num[high]) { // Not rotated
return num[low];
}
while (true) {
if (high == low) { // Cases like [1]
return num[low];
} else if (high - 1 == low) {
return Math.min(num[high], num[low]);
}
int mid = (low + high) / 2;
if (num[low] > num[mid]) {
high = mid;
} else {
low = mid;
}
}
}
``````

Reason why it works:
Since we are looking for the smallest, when we see the arr[0] > arr[mid], then the pivot must be somewhere between these two elements. Otherwise it's in the other half. Apply this recursively and we will get the solution. Although it's accepted, I am still not 100% clear about the edge cases, so please correct me if any part of this code is unnecessary. Thanks!

• The same idea but I think it is simplier. We just need to stop when the size of the interval is 2.

``````public class Solution {
public int findMin(int[] num) {
int n = num.length;
if(num[0] < num[n-1])
return num[0];

int l = 0, r = n-1;

while (r-l > 1) {
int m = (l+r)/2;
if(num[l] < num[m])
l = m;
else
r = m;
}

return Math.min(num[l], num[r]);
}
}``````

• This looks good, but should take care of edge cases:

1. n = num.length == 0; your code will throw exception.
2. n = num.length == 1; your code will work, maybe by luck :)

• I did.

1. When num.length == 0. The signature "public int findMin(int[] num)" of the method requires you to return "int". It is value type. Therefore the invariant is if you return a value it should present in the array. But when the array is empty it breaks the invariant. If it had been "public Integer findMin(int[] num)" where "Integer" is reference type then you could have been able to return "null" as a value. Therefore the only case for empty array is throwing an exception. My solution throws ArrayIndexOutOfBoundsException:

@Test(expected = java.lang.ArrayIndexOutOfBoundsException.class)
public void test04() {
new Solution().findMin(new int[]{});
}

Which I think is okay for OJ solutions, but for "public production middleware" functions I would add validation num.length == 0 and throw IllegalArgumentException:

``````if(num.length == 0)
throw new IllegalArgumentException("num");
``````

But you should throw an exception.

1. When num.length == 1 I also checked:

@Test
public void test03() {
int[] num = {1};

`````` assertEquals(1, new Solution().findMin(num));
``````

}

It works because it enters neither "if" nor "while" and only parts which works is "return Math.min(num[l], num[r]);" which compares the value with itself.
I did this intentionally in order to avoid extra checks like this:

``````if(num.legth == 1)
return num[0];
``````

I hope it helps.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.