[알고리즘] 이진 탐색에 대해 잠깐 알아보자

시작점과 끝점이 있고 중간을 찾는다. 인덱스 값을 비교해서 가까운 쪽으로 범위를 재설정해 먼쪽은 버린다.

로그 복잡도를 가지고 각 단계 마다 탐색 범위를 2로 나누는 것으로 이해할 수 있다. 

 

매우 넓은 억 단위 이상 탐색 범위에서 최적의 해를 찾아야 하는 경우

데이터를 정렬

// 이진 탐색 소스코드 구현(재귀 함수)
function binarySearch(arr, target, start, end) {
  if (start > end) return -1;
  let mid = parseInt((start + end) / 2);
  if (arr[mid] == target) return mid;
  else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
  else return binarySearch(arr, target, mid + 1, end);
}

//  n(원소의 개수)와 target(찾고자 하는 값)
let n = 10;
let target = 7;
arr = [1, 3, 5, 7, 9, 13, 15, 17, 19];

// 이진 탐색 수행 결과 출력
let result = binarySearch(arr, target, 0, n - 1);
if (result == -1) console.log("원소가 존재하지 않습니다.");
else console.log(`${result + 1}번째 원소입니다.`);

한 뒤에 다수의 쿼리를 날려야 하는 경우 사용한다.

처음에 이해가 안되었던 부분이 아무리 못찾아도 start가 end보다 클 수 있나 싶었는데 역시 chatGPT는 똑똑했다.