Leetcode 34) Find First and Last Position of Element in Sorted Array

16 Sep 2021 in Algorithms

My solution

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int res[]={-1,-1};
        if(nums.length==0 || nums==null){
            return res;
        }
        int left =0;
        int right = nums.length-1;
        while(left+1 <right){
            int mid = left+(right-left)/2;
            if(nums[mid]==target){
                //mid ==0 은 불가능. 이렇게 되려면 left=0,right=0 -> left==right 여야하는데, 글면 이 while에 들어올수없다. 따라서 mid-1해줘도 범위 안 벗어난다.=> 아니네.. left=0, right=1 일떄 가능.. 
                //위에꺼 안되서, 조건을 left+1<right로 바꿈. 이렇게 바꾸면, 원소가 최소 세개일때까지만 돌아가니까
                //left 탐색하는 건 세개있을 때 해야지 오류가 안난다. mid 가 0이되면 안되니까..원소가 두개면 무조건 mid가 0 이되는 상황이 발생한다. 그래서 원소를 세개로 하는게 최소가 되게 해야한다!!!
                if(nums[mid-1]!=target){
                    res[0]=mid;
                    break;}else{
                    right=mid;
                }
            }else if(nums[mid]>target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        //두개 확인
        if(res[0]==-1){
            if(nums[left]==target){
                res[0]=left;
            }else if(nums[right]==target){
                res[0]=right;
            }
        }
        if(res[0]==-1)return res;
        left=res[0];
        right=nums.length-1;
        //여기는 우측만 보면 되니까 left<Right 조건으로도 충분하다. 
        while(left<right){
            int mid = left+ (right-left)/2;
            if(nums[mid]==target){
                if(nums[mid+1]!=target){
                    res[1]=mid;
                    return res;
                }else{
                    left= mid+1;
                }
            }else if(nums[mid]>target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        if(nums[left]==target){
            res[1]=left;
        }

        return res;
    }

}

Other Answer

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int firstOccurance = findTarget(nums, target, true);
        if (firstOccurance == -1) {
            return new int[] {-1, -1};
        }
        
        return new int[] {firstOccurance, findTarget(nums, target, false)};
        
    }
    
    private int findTarget(int[] nums, int target, boolean isFirst) {
        int mid; int left = 0; int right = nums.length - 1;
        while (left <=  right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                if (isFirst) {
                    if (mid == left || nums[mid-1] != target) {
                        return mid;
                    }
                    
                    right = mid - 1;
                } else {
                    if (mid == right || nums[mid + 1] != target) {
                        return mid;
                    }
                    
                    left = mid + 1;
                }
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            
        }
        return -1;
    }
}