이진 검색 알고리즘 (Binary Search Algorithm)

이진 검색 알고리즘 (Binary Search Algorithm)

• 오름차순 (혹은 내림차순)으로 정렬된 배열에서 특정 값의 위치를 찾는 알고리즘
• 시작과 마지막 범위 내에서 중간의 값을 임의로 선택하여 찾고자 하는 값과 비교
• 중간 값이 찾는 값 대비 작다면, 시작 범위를 중간 값으로 설정
• 중간 값이 찾는 값 대비 크다면, 마지막 범위를 중간 값으로 설정

장점

• 특정 값을 찾기 위해 배열의 모든 인덱스를 모두 탐색하는 것 대비, 탐색 범위를 절반씩 줄여나가기 때문에 속도가 빠르다.

단점

• 배열이 정렬되어 있어야 한다.
• 정렬을 위한 연산이 소요 된다.

적용 문제 예시

• 배열 내에서 Target 값과 가까운 3개의 원소를 찾는 문제
  • 모든 원소를 탐색하면 O(n^3)의 Time Complexity인데, 이진 탐색 알고리즘을 사용하면 O(n^2)으로 줄일 수 있다.
  • ex) Leet Code 16. 3Sum Closest