Algorithm | 이진 탐색(이진 검색, Binary search)

이진 탐색(이진 검색, Binary search)

오름차순으로 정렬되어 있는 리스트에서 특정한 값을 찾을 때, 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식이다.

장점: 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다.
단점: 정렬된 리스트에서만 사용할 수 있다.

반복문을 이용한 방법

package com.devkuma.algorithum.programming.search.binary;

public class BinarySearchWhile {

    int search(int[] nums, int target) {
        int startIndex = 0;
        int endIndex = nums.length - 1;

        int middle = 1;

        while (startIndex <= endIndex) {
            middle = (startIndex + endIndex) / 2;
            if (nums[middle] == target)
                return middle + 1;
            else if (nums[middle] > target)
                endIndex = middle - 1;
            else
                startIndex = middle + 1;
        }
        return middle;
    }

    public static void main(String[] args) {
        BinarySearchWhile search = new BinarySearchWhile();

        int[] nums = {15, 28, 65, 67, 88, 92, 100, 150};
        int target = 28;
        int index = search.search(nums, target);

        if (index > 0) {
            System.out.println(target + "은 " + index + "번째 있습니다.");
        } else {
            System.out.println(target + "은 없습니다.");
        }
    }
}

실행 결과:

5은 2번째 있습니다.

재귀 함수를 이용한 방법

package com.devkuma.algorithum.programming.search.binary;

public class BinarySearchRecursion {

    int search(int arr[], int target, int startIndex, int endIndex) {
        if (startIndex > endIndex)
            return -1;

        int middle = (startIndex + endIndex) / 2;
        if (arr[middle] == target)
            return middle;
        else if (arr[middle] > target)
            return search(arr, target, startIndex, middle - 1);
        else
            return search(arr, target, middle + 1, endIndex);
    }

    public static void main(String[] args) {
        BinarySearchRecursion search = new BinarySearchRecursion();

        int[] nums = {15, 28, 65, 67, 88, 92, 100, 150};
        int target = 28;
        int startIndex = 0;
        int endIndex = nums.length - 1;

        int index = search.search(nums, target, startIndex, endIndex);

        if (index > 0) {
            System.out.println(target + "은 " + index + "번째 있습니다.");
        } else {
            System.out.println(target + "은 없습니다.");
        }
    }
}

실행 결과:

28은 2번째 있습니다.

선형 탐색 알고리즘 예제 설명

위에 예제를 사용했던 배열에서 28를 찾는 이진 탐색으로 풀어 쓰면 아래와 같다.

{ 15, 28, 65, 67, 88, 92, 100, 150 }
- 중간 값 : 88 -> 작다 -> { 15, 28, 65, 67 }
- 중간 값 : 43 -> 작다 -> { 15, 28 }
- 중간 값 : 28 -> 종료

최종 수정 : 2022-04-02