[Java] 이분탐색 ,이진탐색

굉장히 효율적인 알고리즘으로, 이 알고리즘을 수행하기 위해서는 기본적으로 정렬이 되어있어야한다.

정렬된 자료구조 안에서 특정 값을 찾을때 절반씩 나누어 값을 찾는다는 것이 핵심적인 아이디어이다.

 

이분탐색은 탐색을 진행할 때마다 탐색 범위를 반으로 줄인다.

분할정복 알고리즘과 유사한데 이분탐색은 분할 정복 알고리즘의 한 예이다.

 

• 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다.
• 찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요가 없기 때문에, 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄일 수 있다.
• 이러한 방법을 반복적으로 사용해 탐색하는 방법이 이진 탐색이다.
• 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합하다.

ex 1) 10억 명이 정렬된 배열에서 이진 탐색을 이용해 특정 이름을 찾는다면 단 30번의 비교만으로 검색이 완료된다.

반면에 순차 탐색의 경우 평균 5억 번의 비교가 있어야 된다.

 

ex 2) 영어 사전에서 단어를 찾는 과정 역시 이진 탐색과 동일하다.

영어 사전을 펼쳐서 찾고자 하는 단어가 현재 페이지에 있는 단어보다 앞에 있는지, 뒤에 있는지를 결정한 다음,

단어가 있는 부분 만을 다시 검색한다.

 

이진 탐색의 구현

1. 탐색의 대상이 되는 자료들이 array[left] 부터 array[right]에 들어있다고 가정하자 (정렬이 되어있어야한다.)

-> 탐색되어야 할 범위는 left ~ right까지가 된다. 

즉 left는 인덱스 0 , right는 (자료구조의 길이 -1) 인덱스값이 들어갈것이다.

 

2. left와 right값을 이용해서 중간값 = mid를 구한다  mid = (left + right) /2 이다.

array[left] ~ array[right] 에서 원하는값에 대한 탐색은

 

array[mid]가 찾는값인지 체크하고 아닐시 array[mid]와 찾는값을 비교해서 

 

찾는값 < mid값 : 찾는값이 중앙값보다 작으니까 right를 mid -1 로 수정해서 찾는범위를 

array[left] ~ array[mid-1] 로 바꿔준다.

 

찾는값 > mid값 : 찾는값이 중앙값보다 크니까 left를 mid +1로 수정해서 찾는범위를

  array[mid+1] ~ array[right]로 바꿔준다.

 

3. 바뀐 배열범위에서 다시 mid를 찾고, mid값이 찾는값인지 체크하고 

아니라면 다시 범위를 줄여주고.....반복한다.

찾거나 

또는

찾지못해서  left > right가 될때까지

( 왼쪽인덱스가 오른쪽인덱스보다 크다는것은 반씩줄여가며 찾다가 마지막값 하나에 left,right,mid 인덱스가 동일하게 있고 그 값마저 찾는값이 아닐때 right가 mid-1이 되면서 left가 더 큰상황이 오거나, left가 mid+1이 되면서 right보다 더 큰상황이 발생한다.)

예시 그림

 

 

이진탐색 코드로 구현

주의할점 -> 찾는 자료구조는 정렬이 되어있는 상태여야한다.

반복문으로 구현

public static int binarySearch(int target, int[] arr) {
    int left = 0;
    int right = arr.length-1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            return mid;
        }
        if (target > arr[mid]) {
            left = mid + 1;
            continue;
        }
        right = mid - 1;
    }
    return -1;
}

예시 백준 10815번

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringBuilder sb = new StringBuilder();
        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());
        while (st.hasMoreTokens()) {
            int input = Integer.parseInt(st.nextToken());
            if (binarySearch(input, arr) == -1) {
                sb.append("0 ");
            }
            else{
                sb.append("1 ");
            }

        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }

    public static int binarySearch(int target, int[] arr) {
        int left = 0;
        int right = arr.length-1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (arr[mid] == target) {
                return mid;
            }
            if (target > arr[mid]) {
                left = mid + 1;
                continue;
            }
            right = mid - 1;
        }
        return -1;
    }
}

 

 

 

 

 

재귀로 구현 -> 참고용 (반복문으로 구현하는게 효율적)

public static int binarySearch(int left, int right,int target, int[] arr) {
    int mid = (left + right) / 2;

    if (left > right) {
        return -1;
    }
    if (arr[mid] == target) {
        return mid;
    }

    if (target > arr[mid]) {
        return binarySearch(mid + 1, right, target, arr);
    }
    else{
        return binarySearch(left, mid - 1, target, arr);
    }

}

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.Map.Entry;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringBuilder sb = new StringBuilder();
        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());
        while (st.hasMoreTokens()) {
            int input = Integer.parseInt(st.nextToken());
            if (binarySearch(0,arr.length-1,input, arr) == -1) {
                sb.append("0 ");
            }
            else{
                sb.append("1 ");
            }

        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }

    public static int binarySearch(int left, int right,int target, int[] arr) {
        int mid = (left + right) / 2;

        if (left > right) {
            return -1;
        }
        if (arr[mid] == target) {
            return mid;
        }

        if (target > arr[mid]) {
            return binarySearch(mid + 1, right, target, arr);
        }
        else{
            return binarySearch(left, mid - 1, target, arr);
        }

    }
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

추가

List 자료구조의 이분탐색

 

[자바] Collections.binarySearch 함수

 

 

참조,출처,더 자세한 정보

[Java] 이분 탐색(Binary Search)

이진탐색 = 이분탐색 (Binary Search) - Java로 구현