이진탐색이란?
이진탐색(Binary Search)은 데이터가 정렬된 상태에서 원하는 값을 찾는 알고리즘입니다.
일정 범위를 선정하고 해당 범위의 중앙값을 가져와, 타겟값과 비교하여 범위를 새로 선정하고 다시 중앙값을 가져와 타겟값을 비교하여 범위를 선정하는 프로세스를 반복합니다.
이러한 이진탐색의 시간복잡도는 O(log n)으로써,
일반적인 선형탐색의 시간복잡도인 O(n)보다 우수합니다.
이진 탐색 과정
먼저, 이진탐색 알고리즘을 사용하는 전제는 대상이 되는 데이터가 정렬이 된 상태여야 합니다.
그렇지 않을 경우, 무한루프에 빠질 가능성이 있습니다.
위 그림은, 1~9까지 오름차순으로 정렬된 데이터 중에서 1을 찾는 과정입니다.
①현재 데이터의 중앙값을 선택
②중앙값>타겟, 중앙값을 기준으로 왼쪽 범위를 선택
③중앙값<타겟, 중앙값을 기준으로 오른쪽 범위를 선택
④타겟값을 찾을 때까지 반복
코드 구현
문제는 다음과 같습니다.
N개의 카드 뭉치 속에서 특정 카드를 가지고 있는지, M번 탐색하는 문제.
N의 최대 범위는 50만이며, 탐색 개수인 M의 최대 범위 또한 50만개이므로, 일반적인 선형탐색으로는 시간복잡도를 초과할 가능성이 큽니다.
그렇기에, 이진탐색을 이용하여 해당하는 카드를 보유하고 있는지 체크해야 합니다.
상단에서 작성한 이진탐색의 구현 원리에 따라서,
카드를 저장한 배열 N을 저장하고, 탐색값 배열인 M을 저장 후, N을 오름차순으로 정렬합니다.
이후 바이너리 서치 함수를 구현하여 M 배열의 원소 x값이 N 배열 내에 존재하는지 탐색합니다.
만약 존재한다면 1을 반환하고, 존재하지 않는다면 0을 반환하도록 합니다.
mid는 시작 원소와 종료 원소의 인덱스를 더한 후에 2를 나눈 값으로 지정합니다.
그리고 N배열의 mid 인덱스 값을 타겟(x)과 비교하여, 값이 일치한다면 그대로 1을 반환.
일치하지 않는다면, 그 크기를 비교하여
x가 더 크다면, 시작점을 mid를 기준으로 오른쪽 원소+1. 즉, 오른쪽 영역을 선택합니다.
x가 더 작다면, 종료점을 mid를 기준으로 왼쪽 원소-1. 즉, 왼쪽 영역을 선택합니다.
이를, low<=high 조건을 만족할 때까지 반복합니다.
반복문이 끝났음에도 일치하는 원소를 찾지 못한다면, N 배열 내에 타겟값이 없는 것이므로 0을 반환합니다.
