Java binary search o( log n )


  • 0
    N

    public class Solution {

    void binarySearch(int[] arr,int low,int high, int[] range, int val){
        if(low <= high){
            int mid  = (low + high) /2;
            if(arr[mid] > val)
                binarySearch(arr, low, mid -1, range, val);
            else if(arr[mid] < val)
                binarySearch(arr, mid +1, high, range, val);
            else{
                int i = mid;
                while((i-1) >= 0){
                    if(arr[i] == arr[i-1])
                        i--;
                    else
                        break;
                }
                range[0] = i;
                i = mid;
                while((i+1) < arr.length){
                    if(arr[i] == arr[i +1])
                        i++;
                    else
                        break;
                }
                range[1] = i;
            }
        }else{
            range[0] = -1;
            range[1] = -1;
        }
    }
    
    public int[] searchRange(int[] nums, int target) {
        int[] range = new int[2];
        if(nums.length == 0){
            range[0] = -1;
            range[1] = -1;
        }
        else
            binarySearch(nums, 0, nums.length-1, range, target);
        return range;
    }
    

    }


Log in to reply
 

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