알고리즘 - 선형탐색, 이진탐색

탐색이란?

특정 데이터의 모음에서 원하는 숫자를 찾아내는 것을 말한다. 탐색을 하는 알고리즘은 다양하게 있으며 그 중에서 현재 자료의 상태에 따라 가장 효율적인 알고리즘을 선택해서 사용할 수 있다.

 

선형 탐색 (linear search)

inear는 직선모양의란 뜻을 가진 단어로서 순차 검색 (sequential search)이라고도 불리는 선형탐색은 원하는 데이터가 발견될 때까지 처음부터 마지막 자료까지 차례대로 탐색하는 것을 말한다.

 

선형 탐색 알고리즘은 정확하지만 아주 효율적이지 못한 방법이다. 운이 좋으면 금방 찾을 수 있지만 운이 나쁘다면 원하는 값을 얻어내기까지 오랜 시간이 걸린다.

 

그리고 이러한 선형탐색의 한계를 느끼면 오히려 자료의 정렬 등이 왜 중요한지 알 수 있다.

 

다만 정렬이 되어있지 않은 자료 등을 탐색할 때는 선형탐색을 이용하는 것이 빠른 방법일 경우도 있다.

 

이진탐색 (Binary Search)

선형탐색이 데이터를 처음부터 마지막까지 차례로 탐색하는 것이라면, 이진 탐색은 데이터 중 가운데 값을 찾은 다음 그 가운뎃 값이 찾아야하는 수보다 크면 절반의 뒤쪽을 버리고, 절반의 앞쪽을 탐색하는 행위를 반복해 답을 찾는 방식을 말한다.

 

예를 들어 1~100을 가진 데이터에서 76을 찾으려면 100을 2분의 1로 잘라서 중간값인 50이 76보다 작으니까 1~50은 버리고 50~100을 찾고 다음 50~100의 중간값이 75를 보고 75가 76보다 작으니 50~75의 값을 버리고 다음으로 75~100사이의 중간값과 76을 대조해서 찾는 방식을 말한다.

 

다만 이진 탐색을 위해선 자료가 정렬되어야 한다는 선제조건이 필요하며, 선형 탐색에 비하면 굉장히 빠른 속도로 자료를 찾을 수있다.