[알고리즘] 이진검색

1. 이진검색

• 오름차순으로 정렬된 리스트(배열)에서 특정한 값의 위치를 찾는 알고리즘이다.
• 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 대소를 비교하는 방식을 채택하고 있다.

1부터 100까지의 수 중에서 하나를 머릿속을 생각을 하고 상대방이 고를때마다 값이 그 수보다 더큰지 작은지 알려준다면, 대부분의 사람들이 직관적으로 중앙 값인 50을 고르고 그다음에 25또는 75를 골라 절반씩 줄여 나갈 것이다. 이러한 방식으로 값을 찾아내는 방법이 이진검색이다.

• 원소 11개가 오름차순으로 정렬된 리스트가 있다고 가정하고 그 안에 값 10을 이진검색으로 찾고자 할때는 다음과 같다.

index	0	1	2	3	4	5	6	7	8	9	10
value	?	?	?	?	?	?	?	?	?	?	?

• 우선 가장 중앙인 index 5번 값을 확인한다.

index	0	1	2	3	4	5	6	7	8	9	10
value	?	?	?	?	?	15	?	?	?	?	?

• 10보다 큰 수가 나왔으므로 좌측의 리스트의 절반구간인 index 2번을 확인한다.

index	0	1	2	3	4	5	6	7	8	9	10
value	?	?	7	?	?	15	?	?	?	?	?

• 10보다 작은 수가 나왔으므로 index 2번보다 우측의 리스트 중앙 값을 확인한다.
• 개수가 짝수개이므로 임의로 선택한다.

index	0	1	2	3	4	5	6	7	8	9	10
value	?	?	7	10	?	15	?	?	?	?	?

2. 이진검색과 선형검색

정렬된 리스트의 크기가 작다면 이진검색 알고리즘과 선형검색 알고리즘의 유의미한 차이는 없지만 배열의 길이가 길어지면 많은 차이가 난다.

• 100개의 값을 갖는 배열에서 각 검색에 필요한 최대 단계수는 다음과 같다.
  선형검색 : 100단계
  이진검색 : 7단계

• 선형검색은 찾고자 하는 값이 마지막 셀에 있거나 마지막 셀의 값보다 크면 모든 원소를 조사해야 한다.

• 이진검색은 한번 검색할 때마다 검색해야 할 셀 중 절반을 제거할 수 있다.

• 정렬된 배열의 크기가 두배 늘어날 때마다 이진검색의 단계수는 1씩 증가한다.

• 원소가 10,000개라면 이진검색은 최대 13단계면 충분하며, 1,000,000개라도 최대 20단계이다.

• 위 그래프와 같이 원소수가 늘어나는 만큼 비례해 검색단계수가 올라가는 선형검색과는 다르게 이진검색은 원소 수가 늘어나더라도 아주 조금씩만 단계가 늘어난다.