[leetcode 34] Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you write an algorithm with O(log n) runtime complexity?

 

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

Example 3:

Input: nums = [], target = 0 Output: [-1,-1]

 

문제 풀이:

투포인터를 사용한다. 동일한 값을 발견하면 범위를 찾는다.

 

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] answer = new int[2];
        
        answer[0] = -1;
        answer[1] = -1;
        
        int start = 0, end = nums.length-1;
        
        while(start <= end){
            int mid = (start + end)/2;
            
            if(nums[mid] < target){
                start = mid+1;

                
            }else if(nums[mid] > target){
                end = mid-1;
      
            }else {
                
                int begin = mid, after = mid;
                while(--begin > -1 && ++after < nums.length){
                    if(nums[begin]!= target || nums[after] != target){
                        break;
                    }
                }
                
                while(begin> -1){
                    if(nums[begin] != target){
                        break;
                    }
                    begin--;
                }
                
                while(after<nums.length){
                    if(nums[after]!=target){
                        break;
                    }
                    after++;
                }
                
                answer[0] = begin+1;
                answer[1] = after-1;
                break;
            }
        }
        
        return answer;
    }
}