이분 탐색(Binary Search)

이분 탐색(Binary Search)은 정렬된 배열에서 특정 값의 위치를 찾는 알고리즘입니다. 이 알고리즘은 배열의 중간 값과 찾고 자 하는 값을 비교하여 탐색 범위를 반으로 줄여나가는 방법을 사용합니다.

이분 탐색의 시간 복잡도는 O(log n)입니다.

Binary Search ( with Javascript )

 function binarySearch(arr, target) {
   let low = 0;
   let high = arr.length - 1;
   while (low <= high) {
     let mid = Math.floor((low + high) / 2);
     if (arr[mid] === target) {
       return mid;
     } else if (arr[mid] < target) {
       low = mid + 1;
     } else {
       high = mid - 1;
     }
   }
   return -1; 
}
// 예제
const arr = [1, 3, 5, 7, 9];
const target = 7; console.log(binarySearch(arr, target)); // 3