C++ 문자열 이진 탐색 완벽 가이드: 개념부터 코드 구현까지

이진 탐색(Binary Search)은 정렬된 데이터에서 원하는 값을 빠르게 찾아내는 대표적인 탐색 알고리즘입니다. 문자열 이진 탐색이란, 사전에 정렬된 문자열 배열이 주어졌을 때 이진 탐색 알고리즘을 활용하여 특정 문자열의 위치를 찾는 기법을 말합니다.

예시로 이해하기

입력 : stringArray = {"I", "Love", "Programming", "tutorials", "point"}
찾을 문자열 = "Programming"
출력 : 인덱스 2에서 문자열 발견
설명 : "Programming"의 배열 내 위치(인덱스)는 2입니다.

입력 : stringArray = {"I", "Love", "Programming", "tutorials", "point"}
찾을 문자열 = "coding"
출력 : -1 (문자열을 찾지 못함)

이진 탐색의 동작 원리

이진 탐색은 배열의 중간 지점을 기준으로 찾고자 하는 원소와 비교한 뒤, 탐색 범위를 절반씩 좁혀 나가는 방식으로 동작합니다. 이러한 분할 정복 방식 덕분에 선형 탐색의 O(n)보다 훨씬 빠른 O(log n)의 시간 복잡도를 가집니다.

숫자 배열뿐만 아니라 문자열 배열에도 동일한 알고리즘을 그대로 적용할 수 있습니다. 차이점이 있다면 비교 연산이 숫자가 아닌 문자열 비교로 수행된다는 점입니다. 문자열 비교는 첫 번째 문자부터 두 문자열의 문자를 하나씩 비교하고, 같다면 다음 문자로 넘어가는 방식으로 진행됩니다.

알고리즘 단계

arrString : 정렬된 문자열 배열
lower = 0 ; upper = n - 1 (배열 길이 - 1)
element : 찾고자 하는 문자열

Step 1 : lower <= upper인 동안 아래 과정을 반복
Step 2 : mid = lower + (upper - lower) / 2
Step 3 : arrString[mid] == element 이면 mid를 반환하고 종료
Step 4 : arrString[mid] < element 이면 lower = mid + 1
Step 5 : arrString[mid] > element 이면 upper = mid - 1
Step 6 : lower > upper가 되면 -1을 반환하고 종료 (원소 없음)

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;

int binarySearchString(string arr[], string x, int n) {
    int lower = 0;
    int upper = n - 1;
    while (lower <= upper) {
        int mid = lower + (upper - lower) / 2;
        int res;
        if (x == (arr[mid]))
            res = 0;
        if (res == 0)
            return mid;
        if (x > (arr[mid]))
            lower = mid + 1;
        else
            upper = mid - 1;
    }
    return -1;
}

int main () {
    string arr[] = {"I", "Love", "Programming" , "tutorials" , "point"};
    string x = "Programming";
    int n = 5;
    int result = binarySearchString(arr, x, n);
    if(result == -1)
        cout<<("Element not present");
    else
        cout<<("Element found at index ")<<result;
}

실행 결과

Element found at index 2

마무리

문자열 이진 탐색은 일반적인 이진 탐색과 로직은 같지만, 비교 연산만 문자열 기준으로 바꿔주면 됩니다. 핵심은 배열이 반드시 사전순으로 정렬되어 있어야 한다는 점입니다. 정렬되지 않은 배열에 이진 탐색을 적용하면 올바른 결과를 보장할 수 없으므로, 필요하다면 std::sort 등을 사용해 먼저 정렬한 후 탐색을 수행하는 것이 좋습니다.