이진탐색

이진 탐색이란 정렬돼 있는 데이터에서 특정한 값을 찾아내는 알고리즘이다. 이진탐색은 이분탐색이라고도 불린다. 이진탐색은 탐색 범위를 반으로 나누어 찾는 값을 포함하는 범위를 좁혀가는 방식으로 동작한다.

이진탐색의 이점

처음부터 하나씩 탐색하는 것을 선형 탐색(linear search)라고 하는데,
이진 탐색은 한번 검사할 때마다 탐색 공간을 절반씩 줄이므로 훨씬 효율적이다.

선형탐색의 시간복잡도는 O(N)인 반면, 이진 탐색의 시간복잡도는 O(logN)이므로 훨씬 시간을 많이 세이브할 수 있다.

이진탐색을 사용할 수 있는 조건

• 무조건 배열/리스트가 정렬되어 있어야한다.
  ex) {2,6,8,4,1,7,9,3,5} (X)
  ex) {1,2,3,4,5,6,7,8,9} (O)

탐색 효율 높이기

분할 정복

분할 정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.
탐색에서는 탐색 공간을 특정 기준에 따라 나누고, 나눈 각 탐색 공간에서 탐색을 이어 나가는 것을 뜻한다.

정렬 기준 정하기

이진 탐색을 위해서는 아무 정렬 방식이나 선택하면 안된다.
중간 값과 정답의 대소를 명확히 구분할 수 있어야 하고, 대소 비교를 하여 정답이 속한 더 작은 범위를 정확히 파악할 수 있어야 한다.
모든 자릿수의 합이 15인 숫자를 찾는데 오름차순으로 정렬하고 이진 탐색을 적용할 수는 없다.
따라서 이진 탐색을 적용하려면 문제에서 요구하는 조건을 정확히 파악한 후, 이에 따른 대소 비교를 구현하여 데이터를 정렬한 후 진행해야 한다.

메서드

배열: Arrays.binarySearch()
리스트: Collections.binarySearch()

단, 코테에서 이것들을 사용하지는 않기 때문에 이진탐색을 직접 구현하는 능력이 필요하다.

그림

보통 범위표기는 [start, end)로 작성할 수 있다.
보통 start는 인덱스를, end는 배열의 길이를 작성한다.
처음에는 불편할 수도 있지만 이러한 표기법은 몇가지 이점을 제공한다.

1. 일관성과 간결성: [start, end) 형태의 반개구간 표기법은 시작 인덱스는 포함하고 끝 인덱스는 포함하지 않는다는 명확한 규칙을 제공한다. 이 방식을 사용하면, 시작점과 끝점 사이의 요소 개수를 계산하기 쉽다. 예를 들어, start = 2, end = 5라면, end - start = 3으로, 해당 범위에 정확히 3개의 요소가 있음을 쉽게 알 수 있다.

2. 범위 오류 방지: end를 실제 존재하는 인덱스의 다음 값으로 설정함으로써, 범위를 넘어서는 인덱스에 접근하는 실수를 방지할 수 있다. 특히, 자바와 같이 배열 범위를 엄격히 검사하는 언어에서는 이러한 방식이 런타임 오류를 예방하는 데 도움이 된다.

정렬 기준 정하기

1. 정렬 방식 선택하기

• 이진 탐색을 위해서는 아무 정렬 방식이나 선택하면 안된다. 만약 모든 자릿수의 합이 15인 숫자를 찾는데 오름차순으로 정렬하고 이진 탐색을 적용할 수는 없다.
  정렬 방식에는 오름차순, 내림차순, 자릿수 순, 사전 순, 모든 자릿수의 합, 심지어는 정렬할 수 있는 데이터 없이 직접 정렬 규칙을 찾아내야 할 때도 있다.

2. 정렬 규칙 찾기

• 이진탐색은 정확한 값을 찾는 것 뿐만 아니라, 정답 조건을 만족하는 값 중 가장 큰 값 혹은 가장 작은 값을 찾는데도 많이 사용된다.
• 정답 조건을 만족하는 값 중 가장 큰 값 혹은 가장 작은 값을 쉽게 찾으려면 다음을 고민해야 한다.
  1) 범위 좁히기
• 정답 조건을 만족하는 값 중 가장 큰 값을 구하는 경우라면, 중간 값을 검사했을 때 정답을 만족하더라도 더 큰 값이 있는지 찾아야 하므로 큰 쪽으로 좁히되, 검사한 중간 값을 포함해서 좁혀야 한다.
• 정답 조건을 만족하는 값 중 가장 작은 값을 구하는 경우라면, 중간 값을 검사했을 때 정답을 만족하더라도 더 작은 값이 있는지 찾아야 하므로 작은 쪽으로 좁히되, 검사한 중간 값을 포함해서 좁혀야 한다.

2) 범위 표기법
찾고자 하는 값이 정답 조건을 만족하는 값 중 가장 큰 값: [start, end)
찾고자 하는 값이 정답 조건을 만족하는 값 중 가장 작은 값: [start, end]

// 가정: arr[] = {1, 2, 3, 4, 4, 5}, target = 4
int start = 0, end = arr.length; // arr.length = 6
while (start < end) {
    int mid = start + (end - start) / 2;
    if (arr[mid] <= target) {
        start = mid + 1; // 조건을 만족하면, start를 오른쪽으로 이동
    } else {
        end = mid;
    }
}
// start - 1이 조건을 만족하는 가장 큰 값의 인덱스
return start - 1;

// 가정: arr[] = {1, 2, 2, 3, 4, 5}, target = 2
int start = 0, end = arr.length - 1; // arr.length - 1 = 5
while (start <= end) {
    int mid = start + (end - start) / 2;
    if (arr[mid] < target) {
        start = mid + 1; // 조건을 만족하지 않으면, start를 오른쪽으로 이동
    } else {
        end = mid - 1; // 조건을 만족하면, end를 왼쪽으로 이동
    }
}
// start가 조건을 만족하는 가장 작은 값의 인덱스
return start;

가장 작은 값을 찾을 때 [start, end] 사용 이유:
가장 작은 값을 찾는 경우, 우리는 조건을 만족하는 범위 내에서 가능한 가장 왼쪽(즉, 가장 작은 인덱스)에 있는 원소를 찾으려고 한다. [start, end] 방식을 사용하면, 탐색 범위를 점점 좁혀갈 때 조건을 만족하는 원소가 나타나는 첫 순간의 위치를 정확히 파악할 수 있다.

이유: [start, end] 방식에서는 start와 end가 조건을 만족하는 원소를 정확히 감싸는 형태로 좁혀진다. 조건을 만족하는 첫 번째 원소에 도달했을 때, 탐색을 종료하고 start 또는 end를 반환하면, 그 값이 조건을 만족하는 가장 작은 값의 인덱스가 된다.

가장 큰 값을 찾을 때 [start, end) 사용 이유:
가장 큰 값을 찾는 경우, 조건을 만족하는 범위 내에서 가능한 가장 오른쪽(즉, 가장 큰 인덱스)에 있는 원소를 찾으려고 한다. [start, end) 방식을 사용하면, end를 탐색 범위의 바깥으로 설정하여, 조건을 만족하는 마지막 원소의 인덱스를 정확하게 찾을 수 있다.

이유: [start, end) 방식에서는 end가 항상 탐색 범위 바깥을 가리키게 된다. 이 방식에서는 탐색 과정에서 start가 조건을 만족하는 마지막 원소의 다음 위치로 이동하게 된다. 따라서, 탐색이 종료될 때 start - 1이 조건을 만족하는 가장 큰 값의 인덱스가 된다.

핵심 요약:
가장 작은 값을 찾을 때는 [start, end] 방식을 사용하여 조건을 만족하는 가장 왼쪽 원소를 정확히 찾을 수 있도록 한다. 이 방식은 탐색 범위를 정확히 조절하여 조건을 만족하는 첫 번째 원소에 도달했을 때 탐색을 종료한다.
가장 큰 값을 찾을 때는 [start, end) 방식을 사용하여 조건을 만족하는 가장 오른쪽 원소를 정확히 찾을 수 있도록 한다. 이 방식은 end를 탐색 범위 바깥으로 설정하여, 조건을 만족하는 마지막 원소의 인덱스를 찾을 때까지 탐색 범위를 조절한다.

코드

public class BinarySearchExample {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5}; // 탐색할 배열
        int target = 3; // 찾고자 하는 값

        int result = binarySearch(arr, target);

        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found.");
        }
    }

    public static int binarySearch(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1; // 배열의 실제 끝 인덱스로 설정

        while (start <= end) {
            int mid = start + (end - start) / 2; // 오버플로우 방지를 위해 이와 같이 계산

            // 1. value == target 일 때
            if (arr[mid] == target) {
                return mid; // 탐색 성공: 해당 인덱스 반환
            }
            // 2. value > target 일 때
            else if (arr[mid] > target) {
                end = mid - 1; // 탐색 범위를 앞쪽 절반으로 조정
            }
            // 3. value < target 일 때
            else {
                start = mid + 1; // 탐색 범위를 뒤쪽 절반으로 조정
            }
        }

        return -1; // 찾고자 하는 값이 배열에 없으면 -1 반환
    }
}

기타 팁

당연히 모든 경우에 이분탐색을 할 수 있는 것은 아니다.
경우에 따라 접근 방식이 다르다.

1) 가운데 위치에서 조건을 만족하는 경우, 즉 51~100까지 조건을 만족하는 경우 앞쪽 절반을 남겨도 된다.

2) 만약 가운데 위치에서 조건을 만족하지 않는 경우라면, 앞/뒤 중 어디에 조건을 만족하는 수가 나올지 모르기 때문에 그 다음에 어떻게 할지는 문제의 성격에 따라 잘 생갹해봐야 한다.

3) 만약 "어떤 X에 대해, 그 앞 위치는 모두 X다."가 참이라면, 뒤쪽 절반만 남겨도 된다.
ex) [1,2,3,4,5,6,7,8,9,10] 에서 8을 찾는다고 가정하자.
중간값 5는 X, 즉 조건을 만족하지 않으므로 1~5까지 없애고 뒤쪽 절반만 남겨도 된다.

Q) 이분탐색을 할 때 중간값 X가 조건을 만족하지 않을 때, 찾고자 하는 값이 X의 앞 또는 뒤 둘 다 있을 가능성이 존재하는가?

A)
이분 탐색에서 중간값 (X)가 조건을 만족하지 않을 때, 찾고자 하는 값이 (X)의 앞 또는 뒤에 있을 가능성이 존재하는지 여부는 찾고자 하는 조건의 성격에 따라 다르다. 여기서 중요한 것은 찾고자 하는 조건이 어떤 성격을 가지고 있느냐이다.

1. 단순 값 찾기
   이분 탐색의 가장 기본적인 사용 예는 정렬된 배열에서 특정 값을 찾는 경우이다.
   이 경우, 중간값 (X)가 찾고자 하는 값과 일치하지 않으면, 찾고자 하는 값은 (X)의 앞 또는 뒤 어느 한 쪽에만 존재할 수 있다.
   이때는 (X)가 찾고자 하는 값보다 크면 찾고자 하는 값은 (X)의 앞쪽에, (X)가 찾고자 하는 값보다 작으면 (X)의 뒤쪽에 있을 것이다.

2. 조건을 만족하는 첫 번째 혹은 마지막 위치 찾기
   이분 탐색을 사용하여 특정 조건을 만족하는 첫 번째 또는 마지막 위치를 찾는 문제에서는, 중간값 (X)가 조건을 만족하지 않을 때 (X)의 앞쪽, 뒤쪽 모두에 조건을 만족하는 값이 존재할 수 있다.

결론적으로, 이분 탐색을 할 때 중간값 (X)가 조건을 만족하지 않는 경우, 찾고자 하는 값 또는 조건을 만족하는 위치가 (X)의 앞 또는 뒤에 존재할 가능성이 있는지는 찾고자 하는 문제의 성격에 따라 달라진다.
따라서, 이분 탐색을 적용하기 전에 문제의 조건을 정확히 이해하고, 탐색 로직을 그에 맞게 설계해야 한다.

---

출처: https://www.youtube.com/watch?v=F6lKjRDlOpk
프로그래머스 코딩 테스트 문제풀이전략 자바편