결정 알고리즘 / 이진탐색(이분탐색)

들어가며

알고리즘 공부 중에 새롭게 알게 된 결정 알고리즘과 이진분석에 대해 작성하였습니다.

결정 알고리즘

결정알고리즘이라는 용어는 제가 사용한 것입니다.
답을 정하고 이 답이 유효한지 확인해 가면서 더 좋은 답을 찾아가는 방식입니다.

결정 알고리즘이란 용어는 제가 보고 있는 알고리즘 강의에서 처음 접하였습니다. 강사분께서 '결정 알고리즘이란 무엇인가요?' 라는 질문에 위와 같은 답을 주셨고, 이걸 chatGPT랑 같이 조금 더 다듬어서 정리해보았습니다.

결정 알고리즘이란 어떤 값이 가능한가 불가능한가를 판별하는 알고리즘 입니다. 즉, 주어진 값이 어떤 범위 내에서 탐색 가능한지, 유효한지를 판단하는데 사용됩니다. 주로 이진 탐색을 이용해서 구현합니다. 이진 탐색의 경우 명확한 범위가 주어지며, 범위 내에서 답을 찾아가기 때문에 결정 알고리즘을 구현하는데 매우 용이합니다.

이진탐색

이진탐색은 정렬된 배열에서 원하는 값을 빠르게 찾는 값입니다. 다음 순서로 진행됩니다.

1. 배열을 반을 나눕니다.
2. 중간값 기준으로 탐색 대상이 큰지 작은지 비교합니다.
3. 만약 크다면 작은쪽 배열을 버리고 큰쪽 배열을 다시 나눕니다.
4. 다시 그 배열의 준간 값을 기준으로 탐색대상이 큰지 작은지 비교합니다.
5. 위의 과정을 반복하여 탐색 대상을 찾습니다.

이진탐색 구현

java에서 이진 분석은 직접 구현 가능하고, 또는 내장 메서드를 이용할 수도 있습니다.

직접 구현

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

        while (left <= right) {
            int mid = left + (right - left) / 2;  // 중간 인덱스

            if (arr[mid] == target) {
                return mid;  // 찾았음
            } else if (arr[mid] < target) {
                left = mid + 1;  // 오른쪽으로 이동
            } else {
                right = mid - 1;  // 왼쪽으로 이동
            }
        }
        return -1;  // 못 찾았음
    }

    public static void main(String[] args) {
        int[] data = {1, 3, 5, 7, 9, 11};  // 반드시 정렬된 배열!
        int target = 7;

        int index = binarySearch(data, target);
        if (index != -1) {
            System.out.println("찾음: 인덱스 = " + index);
        } else {
            System.out.println("값 없음");
        }
    }
}

내장 메서드 사용

import java.util.Arrays;

public class BuiltInBinarySearch {
    public static void main(String[] args) {
        int[] data = {1, 3, 5, 7, 9, 11};
        int target = 7;

        int index = Arrays.binarySearch(data, target);
        if (index >= 0) {
            System.out.println("찾음: 인덱스 = " + index);
        } else {
            System.out.println("값 없음");
        }
    }
}

마치며

읽어주셔서 감사합니다.

---

참고자료

[결정 알고리즘]

결정알고리즘이 어떤건가요?
이분 탐색과 결정 알고리즘

[이진 탐색]

How to Do a Binary Search in Python