Java easy understand binary search solution


  • 0
    O
    public class Solution {
        //O(logN)
        public static int search(int[] nums, int target) {
            if(nums.length == 0) return -1;
            int start = 0;
            int end = nums.length - 1;
            return helper(nums, target, start, end);
        }
    
        public static int helper(int[] nums, int target, int start, int end){
            if(start == end && nums[start] == target) return start;
            while(start < end){
                if(end - start == 1){
                    if(nums[start] == target) return start;
                    if(nums[end] == target) return end;
                    return -1;
                }
                int mid = start + (end - start)/2;
                if(nums[mid] == target) return mid;
                if(nums[start] > nums[end]){
                    if(nums[mid] > nums[start]){
                        if(target >= nums[start] && target < nums[mid]) return binarySearch(nums, target, start, mid);
                        start = mid;
                    }else{
                        if(target > nums[mid] && target <= nums[end]) return binarySearch(nums, target, mid, end);
                        end = mid;
                    }
        
                }else{
                    return binarySearch(nums, target, start, end);
                }
            }
            return -1;
        }
    
        public static int binarySearch(int[] nums, int target, int start, int end) { // search target in sorted unrotated subarray
            if(start == end && nums[start] == target) return start;
            while(start <= end){
                int mid = start + (end - start)/2;
                if(target > nums[mid]){
                    start = mid + 1;
                }else if(target < nums[mid]){
                    end = mid - 1;
                }else{
                    return mid;
                }
            }
            return -1;
        }
    }
    

Log in to reply
 

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