Binary Search Solution in Java

  • 0

    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!

  • 2

    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;
                    r = m;
            return Math.min(num[l], num[r]);

  • 0

    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 :)

  • 0

    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:

      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.

Log in to reply

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