34. Find First and Last Position of Element in Sorted Array

Posted on | Edited on | Views:

LeetCode

Binary Search + Linear Search, Time Complexity: O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    // O(logN)
    private int binarySearch(int[] nums,int target,int l,int r){
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[mid]==target) return mid;
            else if(nums[mid]>target) r=mid-1;
            else l=mid+1;
        }
        return -1;
    }
    // O(N)
    private int[] util(int[] nums,int x){
        int l=x,r=x;
      
        while(l>=0&&nums[l]==nums[x]) l--;
        while(r<=nums.length-1&&nums[r]==nums[x]) r++;

        return new int[]{l+1,r-1};
    }
    public int[] searchRange(int[] nums, int target) {
        int x=binarySearch(nums,target,0,nums.length-1);
        if(x==-1) return new int[]{-1,-1};
        else return util(nums,x);
    }
}

Binary Search on left and right branch, Time Complexity: O(logN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    private int binarySearch(int[] nums,int target,boolean left,int l,int r){
        while(l<r){
            int mid=l+(r-l)/2;
            if(nums[mid]==target){
               if(left){
                 r=mid;   
               }else {
                    l=mid+1;
                }
            }else if(nums[mid]>target){
                r=mid-1;
            }else{
              l=mid+1;  
            } 
        }
        if(!left&&nums[l]!=target) l-=1;
        return nums[l]==target?l:-1;
    }

    public int[] searchRange(int[] nums, int target) {
        if(nums==null||nums.length==0) return new int[]{-1,-1};
        int l=binarySearch(nums,target,true,0,nums.length-1);
        if(l==-1) return new int[]{-1,-1};
        int r=binarySearch(nums,target,false,0,nums.length-1);
        return new int[]{l,r};
    }
    /*
    private int binarySearch(int[] nums,int target,boolean left,int l,int r){
        while(l<r){
            int mid=l+(r-l)/2;
            if(nums[mid]==target){
               if(left){
                 r=mid;   
               }else {
                    l=mid;
                    if((r-l)==1&&nums[l]==nums[r]) return r;
                    if((r-l)==1&&nums[l]!=nums[r]) return l;
                }
            }else if(nums[mid]>target){
                r=mid-1;
            }else{
              l=mid+1;  
            } 
        }
        return nums[l]==target?l:-1;
    }*/

0%