[Algorithm] 이진 검색

 

 

선형 검색은 검색 알고리즘에서 성능이 굉장히 안 좋은 알고리즘이다.

물론 데이터 양이 적으면 별반 차이는 없고 찾고자 하는 값이 제일 맨 앞에 위치해 있으면 선형 검색이 더 빠를 수 있다.

 

평균적으로 검색하는 데이터가 많다고 가정하면 이진 검색은 성능이 좋은 검색 알고리즘이다.

 

---

 

 

이진 검색의 역사

 

  이진 검색은 John Mauchly와 John von Neumann이 설계한 초기 컴퓨터 알고리즘 중 하나로 거슬러 올라간다. 이진 검색의 기본 개념은 그보다 훨씬 이전이다.

  이진 검색이 처음 문서화된 사례는 1946년 Derrick Henry Lehmer가 쓴 "Mathematical Tables and Other Aids to Computation"에 기록되어 있다.  이진 검색은 컴퓨터 과학의 발전과 함께 정렬된 데이터 검색에서 중요한 역할을 하게 된다.

 

 

---

 

 

 

이진 검색의 기능

 

  선형 검색은 데이터가 적거나 찾고자 하는 값이 제일 맨 앞에 있다면 검색 횟수가 굉장히 적은 검색 알고리즘 중 하나이다.

  하지만 선형 검색은 데이터 양이 많아지면 검색 효율이 굉장히 떨어진다.

  이진 검색(Binary Search) 알고리즘을 사용하려면 반드시 정렬된 데이터여야 한다.

  이진 검색은 정렬된 데이터에서 특정 값을 빠르게 찾는 알고리즘이다.

 

  이진 검색은 동작 원리는 간단하다 우선 이진 검색을 하기 위해서 배열의 왼쪽을 참조하는 변수, 오른쪽을 참조하는 변수 (왼쪽+오른쪽)/2 가운데 값을 참조하는 변수 총 3개의 변수로 동작한다.

 

 

  1. 배열의 가운데 값을 가져온다.

  2. 가운데 값과 찾고자 하는 값을 비교한다.

      가운데 값이 찾고자 하는 값보다 작으면 배열의 오른쪽 구간을 탐색한다.

      가운데 값이 찾고자 하는 값보다 크면 배열의 왼쪽 구간을 탐색한다.

  

  3. 값을 찾거나 왼쪽과 오른쪽을 참조하는 변수가 같아질 때까지 위 과정을 반복한다.

 

 

 

이진 검색 시간 복잡도

  

  이진 검색은 O(log n)이다. 

  

 

 

---

 

그림으로 설명한 이진 검색 동작

 

 

 

 

---

 

이진 검색 코드

 

 

 

  우선 무조건 정렬된 배열이어야 한다.

import java.util.Scanner;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {5, 10, 15, 20, 25, 30};
        Scanner sc = new Scanner(System.in);
        System.out.print("찾고자하는 값은?: ");
        int key = sc.nextInt();
        search(arr, key);

    }

    static void search(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int center = (left + right) / 2;
            if (arr[center] < key) {
                left = center + 1;
            } else if (arr[center] > key) {
                right = center - 1;
            } else {
                System.out.println("arr[" + center + "]에 존재");
                return;
            }
        }
        System.out.println("해당 값은 없습니다.");
    }
}

 

 

 

---

 

 

상세한 이진 검색 코드

 

 

 

 

import java.util.Scanner;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {5, 10, 15, 20, 25, 30};
        Scanner sc = new Scanner(System.in);
        System.out.print("찾고자하는 값은?: ");
        int key = sc.nextInt();
        search(arr, key);

    }

    static void search(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            
            for (int i : arr) {
                System.out.print(i + " ");
            }
            System.out.println();

            int center = (left + right) / 2;

            for (int i = 0; i < arr.length * 3; i++) {
                double d = (double) i / 3;
                if (d == center) {
                    System.out.print("*");
                    continue;
                }
                System.out.print("=");
            }
            
            System.out.println("가운데 값: " + center);
            
            
            if (arr[center] < key) {
                left = center + 1;
            } else if (arr[center] > key) {
                right = center - 1;
            } else {
                System.out.println("arr[" + center + "]에 존재");
                return;
            }
        }
        System.out.println("해당 값은 없습니다.");
    }
}

 

 

 

---

 

 

Overflow로 인해 코드 수정

 

  (left+right)/2는 java에서 int형 변수는 대략 -21억~21억까지의 숫자를 넣을 수 있다. 여기서 만약 left와 right가 20억 정도라면 위 연산은 overflow가 발생한다.

 

    static void search(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int center =  left+(right-left)/2;  //수정부분 
            if (arr[center] < key) {
                left = center + 1;
            } else if (arr[center] > key) {
                right = center - 1;
            } else {
                System.out.println("arr[" + center + "]에 존재");
                return;
            }
        }
        System.out.println("해당 값은 없습니다.");
    }

 

 

  left+(right-left)/2 가 관례처럼 쓰인다.