[JavaScript]34. Find First and Last Position of Element in Sorted Array - 쉬운설명

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

 

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

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

You must 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]

 

계획

문제 해결 전략

 

이 문제의 목표는 타겟넘버가 nums에 위치하는지 먼저 확인하고 있다면 그 인덱스 범위를 array형식으로 리턴해야합니다. 

 

만약 타겟넘버가 없다면 [-1, -1]을 리턴해야합니다. 

 

문제는 쉽지만 O(log n)속도인 코드로 짜야하기때문에  Medium문제인것같습니다. 

 

 

 

구현 전략

 

 

 

해설

function searchRange(nums, target) {챠ㅐㅠㅊ챠ㅠㅊ
      
      let res = [-1, -1];

      // find the left
      let l = 0;
      let r = nums.length - 1;
        
    //heapify같이 점점 mid pointer를 기준으로 타겟보다 작은지 큰지 비교
    //만약 midpointer가 타겟보다 작다면, left pointer를 증가 
    //반대로 mid pointerr가 타겟보다 크다면 right pointer감소 
      while (l < r) {//좁혀가며 결국 크로스되는시점 
        const mid = Math.floor((l + r) / 2);  // 중간값인덱스 구하기
        console.log(mid)
        if (nums[mid] < target) l = mid + 1; //accending order로 나타내기때문에, 만약 l포인터값이 타겟보다 작다면
          //l 포인터인덱스를 1늘린다. 
        
        else r = mid;
          
      }
    //왼쪽찾기
      if (nums[l] !== target) return res;
    
      else res[0] = l;

    //오른쪽 찾기
      r = nums.length - 1;  // no need to set l to 0

      while (l < r) {
        const mid = Math.ceil((l + r) / 2);   // note using Math.ceil
        console.log("2"+mid)
        if (nums[mid] > target) r = mid - 1;
        else l = mid;
      }

      res[1] = r;

      return res;
}