Accepted Binary Search With O(logN) in JAVA. Beats 70%


  • 0
    K
    1. Identify which side of the array is unsorted from the mid
    2. If the target is under the sorted side of the array, find the index of the target via binary search and return the index
    3. If the target is under the unsorted side of the array, continue to step 1
    public int search(int[] arr, int target) {
            if(arr.length == 1 && arr[0] == target) return 0;
            int low = 0, high = arr.length-1;
            while(low < high) {
    			int mid = low + (high - low) / 2 ;
    			if(arr[mid] == target) { return mid; }
    			if(arr[low] == target) { return low; }
    			if(arr[high] == target) { return high; }
    			
    			if(arr[mid] > arr[high] && arr[mid] > arr[low]) {
    				if(target < arr[mid] && target > arr[low]) {
    					// do binary search on left since the array on left is sorted.
    					return binarySearch(arr, low, mid-1, target);
    				}
    				low = mid;
    			}
    			else if(arr[mid] < arr[low] && arr[mid] < arr[high]) {
    				if(target > arr[mid] && target < arr[high]) {
    					// do binary search on right since the array on right is sorted.
    					return binarySearch(arr, mid+1, high, target);
    				}
    				high = mid;
    			}
    			else {
                                // the array is not rotated. do binary search
    			    return binarySearch(arr, low, high, target);
    			}
    		}
    		return -1;
    	}
    	
    	private int binarySearch(int[] arr, int low, int high, int target) {
    		while(low < high) {
    			int mid = low + (high - low) / 2 ;
    			if(arr[mid] == target) { return mid; }
    			if(arr[low] == target) { return low; }
    			if(arr[high] == target) { return high; }
    			if(target > arr[mid] && low != mid) low = mid;
    			else if (target < arr[mid] && high != mid) high = mid;
    			else break;
    		}
    		return -1;
    	}
    

Log in to reply
 

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