[자료구조] 탐색 알고리즘 (선형탐색 & 이분탐색)

옛날에 집에서 어떤 책이 다음날 꼭 필요해서 찾으려고 보면 보이지 않는 일이 종종 있었다.

결국 집의 모든 책장을 하나하나 뒤져서 찾아내거나, 몇번씩이나 반복해서 찾아봤지만 찾을 수 없었던 기억이 있다.

당시에는 인터넷 검색처럼 딱 책 제목을 찾으면 어딨는지 마법처럼 알아내면 좋을 것 같다는 생각을 한 적이 있다.

컴퓨터과학을 전공하니 이제는 컴퓨터로 똑같은 짓을 종종한다. 물론 직접 찾지는 않고 컴퓨터가 대신 찾기는 한다.

 

기초적인 탐색 알고리즘

가장 기초적인 탐색 알고리즘은 Linear Search(선형 탐색)이다.

말 그대로 있는 데이터를 처음부터 끝까지 순회하면서 찾아내는 방법이다.

컴퓨터는 1초에 몇십억번 정도의 연산을 할 수 있기 때문에 O(N)인 이 방법을 사용하면 아주 많은 정보라도 몇초 ~ 몇분 정도 기다리면 찾을 지도 모른다. 운이 정말 좋다면 맨 앞에 해당 데이터가 있어 O(1)의 시간이 걸릴 수도 있겠다.

그래서 Linear Search는 best case O(1) , worst case O(N)이다.(그러나 누구도 linear Search가 O(1)이라는 소린 하지 않는다)

22를 찾아보자

 

 

조금 더 빠른 알고리즘

그러나 내가 만든 프로그램이 몇 초 걸려서 데이터를 찾고 있다면 사용자들은 계속 새로고침을 누르거나 더이상 서비스를 이용하지 않을 것이다.

좀 더 빠른 알고리즘이 필요하다.

O(logN)이라면 어떨까?

N이 좀 많아지더라도 빨리 찾을 수 있을것 같다.

그 알고리즘은 이분탐색 알고리즘이다.

숫자 맞추기 게임을 해본 적 있다면 모든 경우에서 가장 최선의 전략은 절반씩 범위를 줄여가며 찾는 방법이다.

과정은 다음과 같다.

 

1. 맨 앞, 맨 뒤 범위를 잡는다.

2. 맨 앞과 맨 뒤의 중간 값을 찾아 target인지 확인한다.

3. target이 아니라면 크기 비교를 해서 맨 앞 또는 맨 뒤 범위를 조정하고 다시 중간 값을 찾는다.

4. target을 찾을 때까지 이 과정을 반복한다.

14를 찾는 과정

눈치가 빠른 사람이라면 벌써 알겠지만 이 알고리즘을 수행하기 위해서는 데이터들이 일정한 기준으로 정렬되어있어야 한다.

그래서 데이터를 추가하거나 삭제하면 계속 정렬을 수행해주어야 하는 불편함이 존재한다.

이분탐색 알고리즘은 단계가 진행될 수록 절반씩 범위가 줄어들기 때문에 logN 시간 안에 찾아낼 수 있다.