이진 탐색이란?
이진탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.
배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값X와 비교한다.
X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다.
동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다.
해당 값을 찾을 때 까지 이 과정을 반복
이진탐색 예시
오름차순으로 정렬된 배열이 있다.
{ 17, 28, 43, 67, 88, 92, 100 }이 배열에서 이진 탐색을 이용하여 43을 찾아보자
첫 번째 시도
우선 가운데 위치한 임의의 값 67을 선택한다.
67을 찾고자 하는 값 43과 비교하면 43 < 67 이므로
43은 67의 좌측에 위치함을 알 수 있다.
두 번째 시도
67을 기준으로 좌측에 있는 배열 값들을 다시 탐색한다.
{ 17, 28, 43 }
마찬가지로 가운데의 28을 임의의 값으로 선택한다.
28 < 42 이므로 28보다 우측에 위치함을 알 수 있다.
세 번째 시도
28의 우측을 기준으로 배열을 다시 설정해보면
{43}
배열의 값이 하나만 남게 되고 확인해보면
43 == 43 으로 원하는 값을 얻을 수 있다.
종료 조건
탐색의 종료 조건은 원하는 값을 찾아내는 것이다.
몇 번째 시도에 찾을 수 있게 될지 모르지만 원하는 값이 존재한다면 언젠가 찾아낼 수 있을 것이다.
하지만 만약 원하는 값이 배열에 존재하지 않는다면 어떻게 종료될까?
탐색하고자 하는 값이 마지막 시도까지 갔음에도 존재하지 않는다면 배열에 찾는 값이 없다는 것으로 판단하고 탐색을 종료한다.
시간 복잡도
위에서 사용했던 배열에 원소 몇 개를 추가해서 다시 17 을 이진 탐색으로 찾아보자.
{ 17, 28, 43, 67, 88, 92, 100, 200 }
중간 값 : 88 -> 작다 -> { 17, 28, 43, 67 }
중간 값 : 43 -> 작다 -> { 17, 28 }
중간 값 : 28 -> 작다 -> { 17 }
중간 값 : 17 -> 종료
이진 탐색이란 이름이 붙여진 이유는 처음에 N개 크기의 배열에서 단계가 하나씩 지나감에 따라 탐색할 배열의 크기가 반씩 줄어들기 때문이다.
위의 예제에서 확인해보면, 맨 처음 원소의 개수가 8에서 4, 2, 1 으로 반씩 점차 줄어드는 것을 확인할 수 있다. 즉, 위의 경우 N=8일 때 탐색이 3회 수행 됐으므로 시간 복잡도는 3이 된다.
일반화하여 생각해보자. N개의 크기 배열을 이진 탐색하면 N, N/2, N/4, N/8, … , 1 으로 실행 될 것이다. 여기서 실행된 탐색의 횟수가 시간 복잡도가 될 것이고 그 값을 K라고 한다면, K는 N에 대해 어떻게 나타낼 수 있을까?
1에 2를 K번 곱하면? N이 된다.
2^K = N
K = log2N
즉, 이진 탐색의 시간 복잡도는 O(logN) 이 된다.
연관문제
숫자카드
