[알고리즘 이론] 11. 이분탐색 / 이진탐색 (Binary Search)

이분 탐색 / 이진 탐색 (Binary Search)

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다.
• 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 과정이다.

원리

1. 처음 범위는 인덱스 0부터 끝까지이고, 이 때 중간 인덱스를 mid로 한다.
2. mid의 값과 찾는 원소를 비교한다.
   1. 찾는 원소와 mid의 값이 같다면 탐색 종료한다.
   2. mid < 찾는 원소 -> start는 mid+1로 하고 다시 반복한다.
   3. mid > 찾는 원소 -> end는 mid-1로 하고 다시 반복한다.
3. 만약 end > start가 된다면 해당 배열에 찾는 원소가 없는 것이다.

코드

1. 반복문
public static boolean BSearch(int[] arr, int n) {
    int start = 0;
    int end = arr.length - 1;
    int mid;

    while(start <= end) {
        mid = (start + end) / 2;
        if (arr[mid] < n) {
            start = mid + 1;
        } else if (arr[mid] > n) {
            end = mid - 1;
        } else {
            return true;
        }
    }
    return false;
}

2. 재귀
public static boolean BSearch(int[] arr, int n, int start, int end) {
    if (left > right) {
        return false;
    }

    int mid = (start + end) / 2;

    if(arr[mid] < n) {
        return BSearch(arr, n, mid + 1, end);
    } else if (arr[mid] > n) {
        return BSearch(arr, n, mid - 1, end);
    } else {
        return true;
    }
}

알고리즘 문제 추천

1. 나무 자르기 (실버 2)

• https://www.acmicpc.net/problem/2805

2. 입국심사 (골드 5)

• https://www.acmicpc.net/problem/3079

3. 사다리 (골드 4)

• https://www.acmicpc.net/problem/2022

참고 자료

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search