이분 탐색 🔎 (Binary Search)

❓공부하게 된 계기

➡️ 다음 알고리즘 스터디 주제인 이분 탐색에 대해서 예습

❗️공부한 내용

1️⃣ 이분탐색이란?

➡️ 순차적 탐색과 비교해보면 정확히 알 수 있다.

① 순차적 탐색 (Sequential Search)

➡️ 처음부터 하나하나씩 비교해가며 끝까지 탐색하는 것이다. 최악의 경우 마지막 데이터 까지 탐색하므로 O(n) 의 시간 복잡도를 가지고 있다.

② 이분 탐색 (Binary Search)

➡️ mid 값을 구해서 계속해서 탐색 범위를 반씩 줄여나가며 탐색하는 것이다. 최악의 경우 Tree 구조에서 마지막 leaf 값까지 내려감으로 O(logN) 의 시간 복잡도를 가지고 있다.

2️⃣ 이분탐색 과정

① 처음 범위는 index 0 에서 끝까지 이다. 이 때의 mid = 배열의 길이 / 2

② mid 값과 찾는 값을 비교한다

1. 찾는 값과 mid 값이 같다면 종료
2. 찾는 값이 mid 값보다 작으면 right = mid-1 로 하고 다시 mid 값 계산
3. 찾는 값이 md 값보다 크면 left = mid+1 로 하고 다시 mid 값 계산

③ 만약 left > right 가 되면 값을 찾지 못한 것이므로 종료

3️⃣ 이분탐색 구현

➡️ 이분탐색 구현 방법에는 반복문과 재귀가 있다.

① 반복문

// 반목문을 통한 구현
public static int BinarySearch_Loop(int[] arr, int n) {
    // int arr[] : 주어진 배열
    // int n : 찾고자 하는 값

    // 과정 ① : 처음 left=0 & 끝 right=arr.length-1;
    int left = 0;
    int right = arr.length-1;
    int mid; // 중간값 선언
    int value;

    while (right >= left) {
        mid = (left + right) / 2;
        value = arr[mid];

        if(value > n) right = mid-1;
        else if(value <n) left = mid+1;
        else return mid; // 중간값 
    }
    return -1; // 찾는 값 없음
}

② 재귀

public static boolean BSearchRecursive(int[] arr, int n, int left, int right) {
    /*
    1. arr : 주어진 배열
    2. n : 찾고자 하는 값
    3. left : 왼쪽 끝 index
    4. right : 오른쪽 끝 index
    */

    // 중지 조건
    if(left > right) return false;

    int mid = (left + right) / 2;

    if (arr[mid] < n) // (1) 찾고자하는 값보다 작은 경우 : 오른쪽으로 이동
        return BSearchRecursive(arr, n, mid +1, right);
    else if (arr[mid] > n) (2) 찾고자하는 값보다 큰 경우 : 왼쪽으로 이동
        return BSearchRecursive(arr, n, left, mid - 1);
    else 
        return true; // 값이 존재하는 경우

}

✏️ 적용 시켜본 예제

🧐 추가로 궁금한 점