[알고리즘 기초] 01_이진 검색

---

본 포스팅은 칸 아카데미 컴퓨터 과학 강좌의 알고리즘 단원을 공부하고 정리한 내용입니다.

---

1. 이진 검색

• 정렬된 리스트에서 원하는 항목을 찾기에 효율적인 알고리즘.
• 후보 범위가 한 항목으로 좁아질 때까지 찾고자 하는 항목을 포함하고 있는 리스트를 반으로 나누는 과정을 계속 반복함.
• 배열에서 어떤 항목을 찾아야 할 때 가장 많이 사용함.

1) 배열에 이진 검색 구현하기 의사코드 

( 출처 : ko.khanacademy.org/computing/computer-science/algorithms/binary-search/a/implementing-binary-search-of-an-array )

• 입력값 : array 배열
• array의 요소의 개수 : n
• 검색 대상의 수 : target
• 결과값 :  array 속 target의 인덱스 값

1. min = 0 이고 max = n-1이라고 합니다.
2. guess의 값은 max와 min의 평균값을 정수가 되도록 버림한 값입니다.
3. array[guess]의 값이 target과 같다면 검색을 멈춥니다. 타겟을 찾았습니다. guess를 결과값으로 반환합니다.
4. 추측값이 더 작다면 즉, array[guess] < target이라면, min = guess + 1으로 바꿉니다.
5. 아니면 추측값이 더 큽니다. 그러면 max = guess - 1로 바꿉니다.
6. 2 단계로 돌아갑니다.

 

2) 이진 검색 실행 시간

• n개의 요소가 있는 배열에서 선형 탐색으로 탐색을 하면 최대 n번의 탐색을 거쳐야 함.
• 이진 탐색에서는 기준값과 배열의 정중앙에 있는 데이터를 비교하여 맞지 않을 경우 배열에 있는 기준값과 일치하지 않는 다른 쪽에 있는 값들은 모두 버림.
• 예 1) 32개 데이터가 있을 경우, 데이터 중간 값 뽑았더니 찾는 값보다 더 커서 이 값보다 큰 값들은 모두 버림. 그럼 남은 16개의 더 작은 값 중에서 탐색을 시작함.
• 예 2) 길이 8인 배열 : 최대 4번 탐색함. (처음에 틀리면 4개 값에서 탐색하고 2,1 순으로 줄임)
• 예 3) 길이 16인 배열 : 최대 5번 탐색함. (처음에 틀리면 8개 값에서 탐색하고 4,2,1 순으로 줄임)

===> 배열이 두 배 커질때마다 최대 탐색 횟수는 한 번 늘어남.

 

• 길이가 n인 배열에 최대 m번 만큼의 탐색이 필요하다고 가정해보면, 길이가 2n인 배열에서는 첫 번째 탐색을 한 다음 탐색 범위가 n으로 절반이 되므로 최대 m번의 탐색만 하면 원하는 값을 받드시 찾게됨.
• 따라서 이 경우 최대 m+1번의 탐색이 필요함.

===> 길이가 n인 배열의 경우에 최악의 경우 추측 횟수는 n에서 시작해 1에 이르기까지 반복적으로 반으로 나누  는 횟수 더하기 1이라고 할 수 있음.

===> 2를 밑으로 하는 n의 로그 ( n에서 1까지 반복적으로 반으로 나누는 횟수를 의미하는 수학 함수)

 

[예제 1] 

길이 : 1000인 배열

: 9~10 사이 값이므로 여기에 1을 더하면 10

즉, 최대 10번의 추측 필요

 

[예제 2]

길이 : 128인 배열

= 8

즉, 최대 8번의 추측 필요

 

[예제 3]

32개 팀이 월드컵에 진출하게 되었습니다. 팀명들을 (배열로) 정렬한다고 할 때, 최악의 경우에서 이진 검색을 활용해 배열 내에서 특정 팀을 찾아내고자하면 몇 개의 항목을 확인해야 할까요?

 

답 : 최대 6개

 

 

 

---

출처 : ko.khanacademy.org/computing/computer-science/algorithms

알고리즘 | 컴퓨터과학 | 컴퓨팅 | Khan Academy