Portfolio

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

Medium

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]

Constraints:

0 <= nums.length <= 105

109 <= nums[i] <= 109

nums is a non-decreasing array.

109 <= target <= 109

풀이

은찬


var searchRange = function(nums, target) {
    const answer = [-1, -1];
    let front = 0;
    let back = nums.length;
    let found = false;
    
    if(!nums.length){
        return answer;
    }
    
    while(front <= back){
        const mid = Math.floor((front + back) / 2);
        
        if(nums[mid] < target){
            front = mid + 1;
        } else if(nums[mid] > target){
            back = mid - 1;
        } else{
            back = mid - 1;
            
            if(nums[mid] === target){
                found = true;    
            }
        }
    }
    
    if(found){
        answer[0] = front;
        
        for(let i = front; i < nums.length; i++){
            if(nums[i] === target){
                answer[1] = i;
            }
        }
    }
    
    return answer;
};

효성


var searchRange = function(nums, target) {
    let low = 0;
    let high = nums.length - 1;
    let mid;
    
    while(low <= high) {
        mid = parseInt((low + high) / 2);
        
        if(nums[mid] === target) {
            let left = mid - 1;
            let right = mid + 1;
            
            while(nums[left] === target) {
                left -= 1;
            }
            while(nums[right] === target) {
                right += 1;
            }
            
            return [left + 1, right - 1];
        }
        
        if(nums[mid] > target) {
            high = mid - 1;    
        } 
        
        if(nums[mid] < target) {
            low = mid + 1;  
        } 
    }
    
    return [-1, -1];
};

알고리즘전사재영123


// 60 ms, faster than 93.96%
const binarySearchLeftIndex = (nums, start, end, target) => {
  let s = start;
  let e = end;

  let mid = Math.floor((e + s) / 2);

  while (s <= e) {
    const now = nums[mid];

    if (now === target) {
      if (nums[mid - 1] === target) {
        return binarySearchLeftIndex(nums, s, mid - 1, target);
      }

      return mid;
    }

    if (now < target) {
      s = mid + 1;
      mid = Math.floor((e + s) / 2);
    }

    if (now > target) {
      e = mid - 1;
      mid = Math.floor((e + s) / 2);
    }
  }

  return -1;
};

const binarySearchRightIndex = (nums, start, end, target) => {
  let s = start;
  let e = end;

  let mid = Math.floor((e + s) / 2);

  while (s <= e) {
    const now = nums[mid];

    if (now === target) {
      if (nums[mid + 1] === target) {
        return binarySearchRightIndex(nums, mid + 1, e, target);
      }

      return mid;
    }

    if (now < target) {
      s = mid + 1;
      mid = Math.floor((e + s) / 2);
    }

    if (now > target) {
      e = mid - 1;
      mid = Math.floor((e + s) / 2);
    }
  }

  return -1;
};

const searchRange = (nums, target) => {
  return [
    binarySearchLeftIndex(nums, 0, nums.length - 1, target),
    binarySearchRightIndex(nums, 0, nums.length - 1, target),
  ];
};