Simple recursive Binary Search Solution


  • 0
    M

    // In rotated array we are looking for tipping point
    [7,8,9,0,1,2,3,4,5,6]
    0 1 2 3 4 5 6 7 8 9

    We find mid of the start and end points. Below will be the three conditions

    1. Array is sorted : a[start] <= a[mid] <= a[end] . Here we just return a[start] as answer
    2. a[start] > a[mid] : It means the array is not sorted in the left half.
      Keep in mind the new end point becomes mid not mid-1 because the element that was small a[mid] may as well be the smallest element
    3. a[mid] > a[end] : It means the array is not sorted in right half.
      Here the new start point is a[mid+1] because the smaller element is further to right.
    public class Solution {
        public int findMin(int[] nums) {
            if(nums == null){return 0;}
            return binarySearchMin(nums, 0, nums.length-1);
        }
        
        private int binarySearchMin(int a[], int start, int end){
            if(start == end){ return a[start];}
            
            int mid = (start + end)/2;
            
            // This is not valid situation in first half of array
            if(a[start] > a[mid]){ return binarySearchMin(a, start, mid); }
            
            // This is not valid situation in second half of array
            if(a[mid] > a[end]){  return binarySearchMin(a, mid+1, end);  }
            
            // If we are here it means the array is sorted
            // a[start] <= a[mid] <= a[end]
            return a[start];
        }
    }
    

Log in to reply
 

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