[알고리즘] 이진탐색 알고리즘

이진탐색 (binary Search) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 사용한다.

중간값을 이용하기 때문에, 배열 내부의 데이터가 정렬되어 있을 때 사용할 수 있다.

 

 

 

<동작 방식>

1. 배열의 중간 값을 가져온다.

 

2. 중간 값과 검색 값을 비교한다

 1) 중간 값이 검색 값과 같다면 종료한다. (mid=key)\

 2) 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색한다. (mid<key)

 3) 중간 값보다 검색 값이 크다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색한다. (mid>key)

 

3. 값을 찾거나 간격이 비어있을 때 까지 반복한다.

 

 

<구현>

1. 반복문으로 구현

int BSearch(int[] arr, int target, int low, int high) {
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == target) return mid;
            else if (arr[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

 

 

2. 재귀함수로 구현

int binarySearch(int[] arr, int target, int low, int high){
        if (low>high){
            return -1;
        }
        int mid= (low+high)/2;
        if (arr[mid]==target) return mid;
        else if (arr[mid]<target) return binarySearch(arr, target, mid+1, high);
        else return binarySearch(arr, target, low, mid-1);
    }

 

 

 

 

예제

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String[] str = s.split(" ");
        int N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);

        String input = br.readLine();
        String[] treeArr = input.split(" ");
        int[] arr = new int[N];

        for (int i = 0; i < treeArr.length; i++) {
            arr[i] = Integer.parseInt(treeArr[i]);
        }

        Arrays.sort(arr);
        int answer = binarySearch(arr, M, arr[0], arr[arr.length - 1]);
        System.out.println(answer);

    }

    public static int binarySearch(int[] arr, int target, int low, int high) {
        int mid = (low + high) / 2;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            int length = arr[i] - mid;
            if (length <= 0) {
                length = 0;
            }
            sum += length;
        }

        if (sum == target) {
            return mid;
        } else if (target < sum) {
            return binarySearch(arr, target, mid + 1, high);
        } else {
            return binarySearch(arr, target, low, mid - 1);
        }
    }

}

시간초과가 떴다 ..!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String[] str = s.split(" ");
        int N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);

        String input = br.readLine();
        String[] treeArr = input.split(" ");
        int[] arr = new int[N];

        for (int i = 0; i < treeArr.length; i++) {
            arr[i] = Integer.parseInt(treeArr[i]);
        }

        Arrays.sort(arr);
        int answer = binarySearch(arr, M, 0, arr[N - 1]);
        System.out.println(answer);

    }

    public static int binarySearch(int[] arr, int target, int low, int high) {
        int result = 0;
        while (low <= high) {
            int mid = (low + high) / 2;
            int sum = 0;
            for (int number : arr) {
                if (number > mid) {
                    sum += (number - mid);
                }
            }

            if (sum >= target) {
                result = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }

}

재귀함수 사용 대신, while 반복문을 사용하여 해결하였다.