이진 탐색이란?

김혁준·2024년 10월 16일

알고리즘

코테스터디

목록 보기

4/6

이진 탐색

탐색 범위를 두 부분으로 분할하면서 찾는 방식이다.
시간 복잡도는 O(logN)이다.

참고 : 순차 탐색(Sequential Search)

순차 탐색은 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 데이터를 차례로 확인하는 방법. 시간 복잡도 O(N)이다.
인덱스 0부터 차례로 탐색하며 원소를 건너뛰는 일이 없이 순차적으로 탐색한다.

진행 과정

우선 정렬을 해야 한다.
start end mid 값을 설정한다.
mid와 내가 구하고자 하는 값과 비교한다.
구할 값이 mid보다 높으면 start = mid +1, 반대면 end = mid -1
start > end 될 때까지 계속 반복한다.

JAVA 코드로 표현

public static int binarySearch(int[] arr, int M) { // arr 배열에서 M을 찾는 이진 탐색 알고리즘
        
        // 오름차순 정렬 먼저 실행
        Arrays.sort(arr);

        int start = 0;
        int end = arr.length - 1;
        int mid = 0;

        while (start <= end) {
            
            // 중간값을 설정
            mid = (start + end) / 2;
            
            // 중간값이 M과 같다면 mid를 반환
            if (M == arr[mid]) {
                return mid;
                // 중간값이 M보다 작다면 start를 mid + 1로 설정
            } else if (arr[mid] < M) {
                start = mid + 1;
                // 중간값이 M보다 크다면 end를 mid - 1로 설정
            } else if (M < arr[mid]) {
                end = mid - 1;
            }
        }
        
        throw new NoSuchElementException("타겟 존재하지 않음");
    }

C++ 코드로 표현

int binsearch(int data[], int n, int key) {
    int start, end;
    int mid;
 
    low = 0;
    end = n - 1;
    while (start <= end) {
        mid = (start + end) / 2;
        if (key == data[mid]) {            //탐색 성공
            return mid;        
        }
        else if (key < data[mid]) {        //탐색 범위를 아래쪽으로
            end = mid - 1;
        }
        else if (key > data[mid]) {        //탐색 범위를 위쪽으로
            start = mid + 1;
        }
    }
    return -1;                            //탐색 실패
}

장점

처음부터 끝까지 돌면서 탐색하는 것보다 훨씬 빠른 장점을 가진다.
이분 탐색의 경우 시간 복잡도가 O(logN)이다.

문제

백준 1920번 수 찾기

https://www.acmicpc.net/problem/1920

알고리즘 [접근 방법]

순차 탐색 또는 이진 탐색을 이용하자.
시간 제한은 2초이므로 약 2억번의 연산 이내로 하면 된다.
N의 최대 값은 1000000이므로 O(n^2)인 알고리즘만 피하자
이진 탐색을 이용하면 약 O(log1000000) ~= 20이다.

풀이방법

이진 탐색을 이용하기 위해 오름차순으로 정렬한다.
그리고 while문을 활용하여 이진 탐색을 실행한다.
start, mid, end를 시작, 중간, 끝 인덱스로 초기화한다.

풀이

public class Main {

    public static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        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++) {
            System.out.println(binarySearch(arr,Integer.parseInt(st.nextToken())));
        }
    }

    static int binarySearch(int[] arr, int target) {
        int start = 0;
        int end = arr.length -1;
        int mid = 0;

        while (start <= end) {
            mid = (start + end) / 2;

            if (target == arr[mid]) {
                return 1;
            } else if (arr[mid] < target) {
                start = mid +1;

            } else if (target < arr[mid]) {
                end = mid -1 ;
            }
        }
        return 0;
    }
}