binary search O(log N) 13ms Java solution


  • 0
    Y

    public class Solution {

    public int search(int[] nums, int target) {
        if(nums.length == 0) return -1;
        if(target == nums[0]) return 0;
        if(target == nums[nums.length - 1]) return nums.length - 1;
        return target > nums[0] ? helper1(nums, target, 0, nums.length-1) : helper2(nums, target, 0, nums.length-1);
    }
    
    public int helper1(int[] nums, int target, int low, int high) {
        while(true) {
            int mid = (low + high) / 2;
            if(nums[mid] == target) return mid;
            if(mid == low || mid == high) break;
            if(nums[mid] < nums[0] || nums[mid] > target) high = mid;
            else low = mid;
        }
        return -1;
    }
    
    public int helper2(int[] nums, int target, int low, int high) {
        while(true) {
            int mid = (low + high) / 2;
            if(nums[mid] == target) return mid;
            if(mid == low || mid == high) break;
            if(nums[mid] > nums[0] || nums[mid] < target) low = mid;
            else high = mid;
        }
        return -1;
    }
    

    }


Log in to reply
 

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