Binary Search JAVA solution with just two conditions


  • 1
    K
    1. If the mid is less than low and high, the min element is in the left sub array
    2. If the mid is greater than low and high, the min element is in the right sub array
    3. If the above two conditions are not true then the min element is found
    4. count variable helps identify whether the input array is rotated or not
        public int findMin(int[] arr) {
                    if(arr.length==1) return arr[0];
                    if(arr.length==2) return (arr[0] > arr[1])?arr[1]:arr[0];
                    int low = 0, high = arr.length-1;
                    int count = 0;
    		while(low < high) {
    			int mid = low + (high - low) / 2 ;
    			if(arr[mid] > arr[high] && arr[mid] > arr[low]) {
    				low = mid;
    				count++;
    			}
    			else if(arr[mid] < arr[low] && arr[mid] < arr[high]) {
    				high = mid;
    				count++;
    			}
    			else {
    				return (count == 0)?arr[0]:arr[mid+1];
    			}
    		}
    		return -1;
        }
    

Log in to reply
 

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