지난 글 : [알고리즘] - 선형 탐색
이진 탐색은 배열에서 데이터를 탐색하는 알고리즘이다. 지난 글에서 배운 선형 탐색과 달리, 데이터가 정렬된 경우에만 적용할 수 있다. 배열의 가운데 있는 데이터와 대상 데이터를 비교해서 대상 데이터가 정중앙보다 오른쪽에 있는지 왼쪽에 있는지를 알 수 있다. 한 번의 비교만으로 탐색해야 할 범위를 반으로 줄일 수 있는 것이다. 이것을 대상 데이터를 찾거나 존재하지 않는다는 것을 알 때까지 반복한다.
1
1 2 3 4 5 6 7 8 9여기서 6을 탐색해보자.
1 2 3 4 5 6 7 8 9
-----먼저 배열의 정중앙에 있는 수를 찾는다. 여기서는 5가 된다.
2
1 2 3 4 5 6 7 8 9
---------5와 탐색할 수인 6을 비교한다. 5 < 6 이므로 대상 데이터(6)가 5보다 오른쪽에 있다는 것을 알았다. 필요가 없어진 숫지는 후보에서 제외한다(1, 2, 3, 4, 5).
3
1 2 3 4 5 6 7 8 9
-----남은 배열의 정중앙에 있는 수를 찾는다. 여기서는 7이 된다.
4
1 2 3 4 5 6 7 8 9
---------7과 6을 비교한다. 6 < 7 이므로 6은 7보다 왼쪽에 있다는 것을 알았다. 필요 없어진 숫자를 후보에서 제외한다(7, 8, 9).
5
1 2 3 4 5 6 7 8 9
-----남은 배열의 정중앙에 있는 수를 찾는다. 여기에서는 6이 된다. 6 = 6 으로 대상 숫자를 발견했다.
이진 탐색은 배열이 정렬돼 있다는 것을 활용해 탐색할 범위를 매번 반씩 줄여나갈 수 있다. 탐색할 범위가 한 개의 데이터가 되면 탐색이 종료된다.
참고 서적 :
