이진 탐색(Binary Search) 알고리즘 개념 및 예제 소스

# 이진 탐색(Binary Search)이란?

* 반씩 범위를 나누어 가면서 분할정복하여 탐색하는 방법

* 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘 (정렬된 데이터가 아니면 적용이 불가능)

* 사전을 찾을 때 사전을 펴서 찾는 단어가 없으면 위치에 따라 앞쪽을 찾거나 뒤쪽을 찾고, 찾을 때까지 그걸 반복하는 걸 생각하면 쉽다.

* 1부터 n까지 숫자중 하나 맞추기 게임을 생각하면 쉽다.

# 선형 자료구조의 대표적인 탐색 방법

* 선형탐색 (Linear Search)

처음부터 하나하나 비교하여 검색하는 방법

장점: 구현하기 쉽고, 정렬이 안되어 있어도 된다.

단점: 검색하는데 시간이 오래 걸린다.

시간 복잡도

최고: O(1), 평균: O(N), 최악: O(N)

* 이진탐색 (Binary Search)

장점: 속도가 빠르다.

단점: 값들이 정렬된 상태이어야 한다.

시간 복잡도

최고: O(1), 평균: O(log N), 최악: O(log N)

# 이진 탐색의 성능

* 탐색 대상의 범위 : 1/2 1/4, 1/16, ... (탐색 대상이 반씩 줄어들게 된다.)

* n : 데이터 집합의 크기

   x : 탐색 반복 횟수

   x = log2n

* 100만개의 데이터 집합 : 최대 20회

* 1000만개의 데이터 집합 : 최대 23회

* 4,294,967,296개(약 43억개)의 데이터 집합: 최대 32회

# 이진탐색 (Binary Search) 과정

1. 데이터 집합의 중앙에 있는 요소 선택

2. 중앙 요소의 값과 찾고자 하는 목표 값을 비교

3. 목표 값이 중앙 요소의 값보다 작다면 중앙을 기준으로 데이터 집합의 왼편에 대해 새로 검색을 수행

   크다면 오른편에 대해 이진 탐색을 새로이 수행

4. 찾고자 하는 값을 찾을 때까지 1번~3번 과정을 반복

# 예제 소스

import java.io.FileInputStream;
import java.util.Scanner;
 
public class BinarySearch_Test {
    static int M; // 배열의 개수
    static int N; // 검색할 숫자의 개수
    static int input[];
 
    static void binarySearch(int input[], int low, int high, int searchValue) {
        // 값을 찾지 못한 경우
        if (low > high) {
            System.out.print("-1 ");
            return;
        }
 
        // 중간 index 구하기
        int mid = (low + high) / 2;
 
        // 1. searchValue < 중간값
        // 2. searchValue > 중간값
        // 3. searchValue == 중간값
        if (searchValue < input[mid]) {
            binarySearch(input, low, mid - 1, searchValue);
        } else if (searchValue > input[mid]) {
            binarySearch(input, mid + 1, high, searchValue);
        } else {
            System.out.print(+mid + " ");
            return;
        }
    }
 
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("C:\\java\\SW\\sample.txt"));
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
 
        for (int test_case = 1; test_case <= T; test_case++) {
            M = sc.nextInt();
            N = sc.nextInt();
            input = new int[M];
 
            for (int i = 0; i < M; i++) {
                input[i] = sc.nextInt();
            }
 
            System.out.print("#" + test_case + " ");
            for (int i = 0; i < N; i++) {
                int searchValue = sc.nextInt();
                binarySearch(input, 0, M - 1, searchValue);
            }
            System.out.println();
        }
        sc.close();
    }
}

# 참고 사이트

https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89

https://www.youtube.com/watch?v=Vfg6-AWGsCw

https://ledgku.tistory.com/35

https://mygumi.tistory.com/72

https://blockdmask.tistory.com/167

https://wayhome25.github.io/cs/2017/04/15/cs-16/