이진 탐색(binary search)은 정렬된 리스트에서 특정 값을 빠르게 찾는 알고리즘

• 알고리즘
  • 리스트를 반으로 나눠서 목푯값이 어느 쪽 절반에 속하는지 결정하고
  • 나머지 절반은 버리면서 목푯값이 포함될 가능성이 있는 절반을 탐색하는 방식
• 정확성과 효율성을 쉽게 분석할 수 있고 속도와 정확성 모두를 보장하며 데이터와 알고리즘의 상호 작용을 잘 보여준다.

Section 01. 문제 정의

N개의 데이터 점 X = {x1, x2, …. , xn}과 목표값 x’ = xi인 xi이 X의 원소일 때 찾거나 그런 점이 없음을 알아내라.

이를 일상생활에서는 이러한 작업을 ‘어떤 것을 찾아줘’라고 표현한다.

Section 02. 선형 스캔

선형 스캔은 리스트에서 한 번에 하나씩 값을 목푯값과 비교하면서 목푯값을 찾거나 목록의 끝에 도달할 때까지 비교해 목푯값을 찾는다.

LinearScan(Array: A, Interger: target):
	Integer: i = 0
	WHILE i < length(A):
		IF A[i] == target:
			return i
		i = i + 1
	return -1

이 코드는 일치하는 원소의 인덱스를 반환하고 탐색에 실패하면 배열에 원소가 없으므로 -1을 인덱스로 반환한다.

• 단일 WHILE 루프는 배열의 각 원소를 반복하고, 내부 IF 문은 인덱스에 해당하는 원소를 목표값과 비교한다.
• 목푯값을 찾은 경우 즉시 해당 인덱스를 반환한다.
• 배열의 끝까지 확인한 경우 -1을 반환한다.

목표가 데이터에 있는지 찾기 위해 가능한 항목을 모두 확인하기 때문에 ‘무식한 검사’다.

/**
 * Performs a linear scan to find the index of the target element in the array.
 *
 * @param {number[]} array - The array to search through.
 * @param {number} target - The target element to find.
 * @returns {number} The index of the target element if found, otherwise -1.
 */
function linearScan(array, target) {
  let i = 0;
  while (i < array.length) {
    if (array[i] === target) {
      return i;
    }
    i = i + 1;
  }
  return -1;
}

// Example usage:
const arr = Array(10).fill(0).map(() => Math.floor(Math.random() * 10))
const target = 3;
console.log(arr)
console.log(linearScan(arr, target)); 

Section 03. 이진 탐색 알고리즘

이진 탐색은 ‘정렬된’ 리스트에서 목표값을 찾는 알고리즘으로, 정렬된 데이터에서만 작동한다.

• 알고리즘은 리스트를 반으로 분할하고 목푯값이 어느 쪽 절반에 속하는지 결정한다.