[Algorithm] 이진검색 (Binary search)

이진검색 (Binary search)

■ 정의

- 이진검색은 요소가 오름차순으로 정렬된 배열인 상태에서 검색하는 알고리즘
- 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색
- 리스트의 중간 부분에 찾는 원소가 있는지 확인, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색    하거나 중간부터 검색

 

■ 사용 예

 - 39를 찾는 과정

1. index 0과 10을 기준으로 2로 나눈 값 index 5를 살펴본다.

2. index 5의 값이 찾으려는 39보다 작으므로 index 5 이하는 더 이상 살피지 않는다.

3. index 6과 10을 기준으로 2로 나눈 값 index 8을 살펴본다.

4. index 8의 값이 찾으려는 39보다 크므로 index 8 이상은 더 이상 살피지 않는다.

5. index 6과 7을 살펴 원하는 값 39를 찾는다.

 

■ 이진 검색 알고리즘의 종료 조건

1. a[pc]와 key 값이 일치 할 경우
2. 검색 범위가 더 이상 없을 경우

 

■ Code

import java.util.Arrays;
import java.util.Scanner;

public class BinSearch {
    static int binSearch(int[] a, int n, int key){
        int pl = 0;
        int pr = n - 1;

        do{
            int pc = (pl + pr) / 2;
            if(a[pc] == key)
                return pc;
            else if(a[pc] < key)
                pl = pc + 1;
            else
                pr = pc - 1;
        }while(pl <= pr);

        return -1;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        System.out.print("요솟수: ");
        int num = sc.nextInt();
        int[] x = new int[num];

       System.out.println("오름차순으로 입력하세요.");

        System.out.print("x[0]: ");
        x[0] = sc.nextInt();

        for(int i = 1; i < num; i++) {
            do {
                System.out.print("x[" + i + "]: ");
                x[i] = sc.nextInt();
            } while (x[i] < x[i - 1]);
        }
        
            System.out.print("검색할 값: ");
            int ky = sc.nextInt();

            int idx = binSearch(x, num, ky);

            if(idx == -1)
                System.out.println("그 값의 요소가 없습니다.");
            else
                System.out.println("그 값은 x[" + idx + "]에 있습니다.");
        }
    }

 

---

Arrays.binarySearch

■ 정의

- 자바에서 제공하는 이진 검색 표준 라이브러리
- 이진 검색 메서드를 직접 작성할 필요가 없음
- 배열 요소의 자료형과 관계없이 검색할 수 있음
- 검색에 실패한 경우, 삽입 포인트를 x라고 할 때 반환값은 -x -1이 됨

 

■ 메소드

1. static int binarySearch(byte[] a, byte key)
2. static int binarySearch(char[] a, char key)
3. static int binarySearch(double[] a, double key)
4. static int binarySearch(float[] a, float key)
5. static int binarySearch(int[] a, int key)
6. static int binarySearch(long[] a, long key)
7. static int binarySearch(short[] a, short key)
8. static int binarySearch(Object[] a, Object key)
9. static <T> int binarySearch(T[] a, T key, Comparator <? super T> c)

 

■ Code

import java.util.Arrays;
import java.util.Scanner;

public class BinarySearchTester {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        System.out.print("요솟수: ");
        int num = sc.nextInt();
        int[] x = new int[num];

        System.out.println("오름차순으로 입력하세요.");

        System.out.print("x[0]: ");
        x[0] = sc.nextInt();

        for(int i = 1; i < num; i++){
            do{
                System.out.print("x[" + i + "]: ");
                x[i] = sc.nextInt();
            }while(x[i] < x[i - 1]);
        }

        System.out.print("검색할 값: ");
        int ky = sc.nextInt();

        int idx = Arrays.binarySearch(x, ky);			// Arrays.binarySearch 사용

        if(idx < 0)
            System.out.println("그 값의 요소가 없습니다.");
        else
            System.out.println("그 값은 x[" + idx + "]에 있습니다.");
    }
}

 

 

---

■ 백준 No.1920

1920번: 수 찾기