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

※ 이 글은 chatGPT를 기반으로 작성한 글입니다.

 

① 이진 검색 알고리즘(binary search algorithm)은 크기가 n인 정렬된 배열 안에 X가 존재하는 지를 탐색하기 위한 알고리즘이다.

  ㉠ 이진 검색 알고리즘은 이분 탐색 알고리즘, 이진 탐색 알고리즘, 이분 검색 알고리즘이라고도 불린다.

② 이진 검색 알고리즘을 이해하기 위한 가장 쉬운 예시로 업 앤 다운(up and down)을 들 수 있다.

  ㉠ 상대는 숫자 한 가지를 생각한다.

  ㉡ x보다 큰가? -> Yes -> x보다 작은 숫자 집합은 정답에서 제외된다.

  ㉢ x보다 큰가? -> No-> x보다 큰 숫자 집합은 정답에서 제외된다.

  ㉣ 정답 x를 찾을 때까지 ㉡과 ㉢을 반복한다.

③ 특정 x를 결정하는 가장 합리적인 방법이 상한과 하한의 평균 값으로 취하는 것이다.

④ 특정 x가 정렬된 배열 내부에 한 개만 존재한다고 가정할 때, 다음 예시를 보자.

  ㉠ 배열의 크기가 1일 때는 상한과 하한이 0이기 때문에 정답은 0일 수 밖에 없다.

 

  ㉡ 배열의 크기가 2일 때는 정답이 0보다 크면 1이 정답이 되고, 작거나 같으면 0이 정답이 된다.

 

  ㉢ 배열의 크기가 3일 때는 정답이 1보다 크면 2가 정답이 되고, 작거나 같으면 ㉡을 수행한다.

 

  ㉣ 배열의 크기가 4일 때는 정답이 1보다 크면 왼쪽 배열을 버리고, 1보다 작거나 같으면 오른쪽 배열을 버린다.

 

  ㉤ 배열의 크기가 n일 때는 정답의 ㉠, ㉡, ㉢, ㉣의 과정을 정답 x를 찾을 때까지 반복하면 된다.

⑤ 이진 검색 알고리즘의 의사 코드(psuedo code)는 다음과 같다.

 

⑥ 배열의 크기가 n일 때 시행이 반복될 수록 배열의 크기가 절반이 되므로, 시간 복잡도는 O(log(n))이다.

 

⑦ 이진 검색 알고리즘의 소스 코드는 다음과 같다.