이분탐색

저장되어있는 데이터를 탐색하는 방법은 크게 두가지로 나뉩니다.

바로 순차탐색과 이분탐색입니다.

 

먼저 순차탐색에 대해 알아 보겠습니다.

 

순차탐색

5 9 2 1 4 3 8 0 7 에서 데이터 2는 몇번째 위치에 존재할까요??

 

0부터0까지의 숫자 중 2를 찾아야하는데 숫자들 서로 연관없이 무작위로 섞여있습니다.

이럴때는 단순하게 앞에서부터 하나씩 데이터를 확인하여 탐색해야합니다.

 

순차탐색은 데이터의 정렬유무에 상관없이 앞에서부터 데이터를 하나씩 확인하여 탐색하는 알고리즘입니다.

 

 

이분탐색

1 3 5 7 9 11 13 15 17 19 21 23에서 데이터 11은어디에 존재하는가?

 

여기에서는 이미 배열의 데이터가 정렬되어있는 상태입니다.

이런 상황에서는 데이터를 더 빠르게 탐색할 수 있습니다. 

이유는 다른 위치에 있는 데이터의 범위를 추측할 수 있기 때문입니다.

예를 들어 9의 오른쪽의 숫자들은 9보다 항상 큽니다.

 

이분탐색은 맨 처음에 중간 위치에서부터 출발한다는 특징이있습니다.

위와 같이 mid 값을 검사하고 만약 찾는 값이 아니면 lt와 rt중에 하나를 mid값으로 바꿉니다.

이유는 그 이후나 이전을 탐색할 필요가 없기 때문입니다.

그리고 mid값은 lt와 rt값의 2를 나눈 값으로 바꾸면 됩니다,

이를 반복하면 lt와rt가 같아지거나 찾는 값이 mid가 되는 상황이 우리가 정답을 찾게되는 것입니다. 

 

이분탐색은 한 번 탐색할 때마다 크기를 반으로 줄여나간다는 점에서 시간 복잡도 O(Log2N)의 시간 복잡도를 가집니다.