Binary Search

정렬되어 있는 배열의 중간에 있는 임의의 값을 선택, 찾고자 하는 값과 비교
중간값보다 작으면 좌측 데이터 대상, 크면 우측 데이터 대상으로 다시 탐색
값을 찾을 때까지 반복

function binarySearch(nums: number[], target: number): number {
  let left: number = 0;
  let right: number = nums.length - 1;

  while (left <= right) {
    const mid: number = Math.floor((left + right) / 2);

    if (nums[mid] === target) {
      return mid;
    }

    if (target < nums[mid]) {
      right = mid - 1;
    }

    left = mid + 1;
  }

  return -1;
}

Date:

Tags: Algo