문제

오름차순인 숫자 nums 배열과 찾아야할 target을 인자로 주면, target이 몇 번째 index인지 return 하라.

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

설명: 찾지 못하면 -1로 return 하라.

nums 배열에 있는 요소는 서로 중복된 값이 없다.

Thinking Algorithm

1. 첫 인덱스와 끝 인덱스를 찾아 중간 인덱스를 구해 각 left와 right에 넣어줌
2. 두 개의 (left,right)처음과 끝값을 이용해 중간 인덱스를 구해 mid에 넣어줌
3. 중간 인덱스로 중간값을 구했으면 타켓값과 비교
   1) 타켓의 값이 중간값과 같으면 바로 리턴
   2) 타켓의 값이 중간값보다 크다면 타겟값이 중간값보다 오른쪽에 있다
   3) 타겟의 값이 중간값보다 작다면 같은 원리로 중간값보다 왼쪽에 있다
4. 반복하다 보면 타겟 값에 가까워지고 반복이 끝날때까지 중간값이 타겟값을 찾지 못하고 left와 right가 만나게 되어 중간값이 없어지면 그 인덱스가 타겟값이 되게됨

Code

const search = (nums, target) => {
  let left = 0
  let right = nums.length -1
  while(left < right){
    let mid = Math.round((left+right)/2)
    if( nums[mid] === target) {
      return mid
    }
    else if(nums[mid] < target) {
      left = mid + 1
    } else if(nums[mid] > target){
      right = mid - 1
    }
  } 
  if(left === right) {
    return right
  }
  return -1
}