이진 검색 - Binary Search

문제. 정수배열 arr과 정수 num을 입력받아 arr안에 num이 있다면 해당요소의 인덱스를 반환하고, 없으면 -1 반환

단, 정수배열 arr은 정렬이 되어있다.

// 1. 정렬된 배열과 값을 입력 받는다.
const binarySearch = (arr, num) => {
  // 2. 배열의 시작 부분에 왼쪽 포인터, 끝부분에 오른쪽 포인터
  let left = 0;
  let right = arr.length - 1
       
  while(left <= right) {
    // 3. 왼쪽 포인터가 오른쪽 포인터보다 앞에 있는 동안 중간 포인터 생성
    let median = Math.floor((right + left) / 2)
    
    // 3-1. 찾고자 하는 값이 중간 포인터라면 해당 인덱스 반환
    if(num === arr[median]) return median
    
    if(num > arr[median]){
      // 3-2. 중간 포인터 값이 작으면 왼쪽 포인터를 올리고
      left = median + 1 
    } else {
      // 3.3 중간 포인터 값이 크면 오른쪽 포인터를 내린다.
      right = median - 1
    }
  }
  // 4. 값을 찾지 못하면 -1 반환
  return -1
}

binarySearch([1,2,3,4,5,6,7,8,9,10,11,12], 5) // 4