알고리즘 / 이분 탐색(이진 탐색)

이분 탐색 알고리즘(Binary Search Algorithm)

 

정의

이미 정렬된 배열에서 탐색 범위를 두 부분 리스트로 나눠 절반씩 좁혀가며

필요한 부분에서만 탐색하도록 제한하여 원하는 값을 찾는 알고리즘이다.

 

동작

이진 탐색은 정렬된 배열이 필요하며, Left, Right, Mid의 변수가 필요하게 된다.

 

Left는 왼쪽 끝 인덱스, Right는 오른쪽 끝 인덱스, Mid는 (Left + Right)/2 로 구할 수 있다.

const binarySearch = (arr, targetValue) => {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === targetValue) {
      return arr[mid];
    }
    else if (arr[mid] > targetValue) {
      right = mid - 1;
    }
    else if (arr[mid] < targetValue) {
      left = mid + 1;
    }
  }
  return -1;
}

1. 찾고자 하는 값과 탐색한 값이 같다면 탐색한 값 반환.
2. mid인덱스의 값 > 찾고자 하는 값 이면 right값을 미드보다 1작은 값으로 설정
3. mid인덱스의 값 < 찾고자 하는 값 이면 left값을 미드보다 1큰 값으로 설정

 

 

시간 복잡도

• 최선 : O(1) 첫 루프에 원하는 값을 찾은 경우
• 평균 : O(log N) 
• 최악 : O(log N)

 

총 정리

• 이진 탐색은 배열에서만 수행 가능
• 배열의 인덱스를 저장하는 left, right, mid가 필요
• mid에 해당하는 배열의 값과 찾고자 하는 값을 비교
• left가 right보다 작거나 같을 때 까지 반복, left가 right보다 커지면 종료