이분 탐색/이진 탐색(Binary Search)이란? (+백준 1920번)
개요
알고리즘 문제를 풀다보니 이진탐색과 관련된 문제이지만, 이진탐색이 아닌 다른 방향으로 풀었던 기억이 있다. 그래서 이번에 이진탐색에 대해 정리하면서 이진탐색 문제가 나왔을 때 바로 떠올릴 수 있도록 해보고자 한다!
이진/이분 탐색이란?
순차적 탐색(선형 탐색)보다 빠른 탐색을 위해 나온 탐색 방법으로 정렬된 배열에서 특정값을 찾는 알고리즘을 의미한다.
탐색범위를 절반으로 줄여나가기 때문에 순차적 탐색에 비해 빠른 속도를 보장한다.
이진 탐색 과정
순차적 탐색(선형 탐색)
정렬된 배열에서 특정 원소를 찾기위해 모든 순차적으로 모든 인덱스를 탐색한다.
이분 탐색
정렬된 배열 안에서 특정원소를 찾을 때 인덱스 LOW값과 HIGH의 중간값을 비교
중간값이 특정원소가 아니라면 중간 값과 비교 후 다시 인덱스 LOW와 HIGH, 중간값을 재설정 (만약, 중간 값 보다 큰 경우라면 절반에서 더 큰 쪽으로 설정)
인덱스 LOW와 HIGH를 재설정할 때 마다 탐색 범위가 절반으로 줄어든다.
과정이 복잡해 보일수도 있으나, 중간값을 찾아 탐색범위를 절반씩 줄여나가기 때문에 for문을 사용해서 전체를 순회하며 값을 찾는 선형 탐색보다 빠른 탐색을 할 수 있다.
이진 탐색의 성능
빅오 표기법에 따른 이진탐색의 시간복잡도는 로그 시간인 O(logn)으로 다른 정렬에 비해 상대적으로 매우 빠르다.
O(logn) : 입력 크기가 증가함에 따라 실행 시간이 로그함수의 형태로 증가한다. 대표적으로 이진탐색 알고리즘이 있다.
예제
https://www.acmicpc.net/problem/1920
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
내가 풀었던 방법은 자료구조 Set을 사용했었다. Set의 경우 중복이 되지 않고, 특정 값을 갖고 있는지 확인하는 절차가 빠르기 때문이었다. 하지만 해당 문제의 카테고리가 이분탐색으로 분류된 만큼 이분탐색을 활용해서 풀어보자.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
//배열 입력받기
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
//정렬해야만 이진탐색이 가능하다.
Arrays.sort(arr);
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine(), " ");
for(int i=0; i<M; i++) {
int key = Integer.parseInt(st.nextToken());
//이진탐색을 위한 인덱스 객체
int low = 0;
int high = arr.length-1;
boolean flag = false; //반복문을 break로 나왔는지, 특정원소가 없어서 나왔는지 확인
//이진탐색 반복문
while(low<=high) {
int mid = (low+high)/2; //중간 인덱스 번호
if(key < arr[mid]) {
high = mid-1;
}
else if(key > arr[mid]) {
low = mid+1;
}
else {
sb.append(1+"\n");
flag = true;
break;
}
}
if(!flag) { //만약 플래그가 false라면(값을 찾지 못하고 끝까지 돌고 나왔다면)
sb.append(0+"\n");
}
}
System.out.println(sb);
}
}
참고자료