31.10 특정 값 검색하기: SEARCH 알고리즘

검색(SEARCH) 알고리즘은 배열 등 데이터에서 특정 값을 검색합니다. 일반적으로 순차 검색과 이진 검색 등으로 구분할 수 있습니다.

이진 검색 알고리즘

이진 검색 알고리즘은 주어진 데이터가 오름차순으로 정렬되어 있다고 가정합니다. 데이터가 정렬되어 있지 않다면, 앞에서 배운 정렬 알고리즘 등을 사용하여 정렬한 후 이진 검색 알고리즘 로직을 적용해야 합니다. 이진 검색 알고리즘을 영어로 divide and conquer(나누기 및 정복) 알고리즘이라고도 하는데, 의미 그대로 데이터를 절반으로 나누어서 검색하여 순차 검색보다 효율이 높습니다.

다음과 같이 1차원 배열에 1, 3, 5, 7, 9 데이터가 있다고 합시다. 9를 검색할 때 이진 검색을 사용하며 중간 인덱스 값을 찾는 것이 핵심 로직입니다. 중간 인덱스를 mid로 놓고 low 인덱스는 0, high 인덱스는 4로 한 후 각 회전마다 중간 인덱스를 구하여 이 값이 찾으려는 데이터인지 비교하면 됩니다.

▲ 그림 31-1 이진 검색 알고리즘 실행 단계