99클럽 코테 스터디 37일차 TIL + 이진 탐색(Binary Search)(2)

학습 키워드

- 이진 탐색(Binary Search)

 

공부한 내용

이진 탐색 예시

---

• 해당 예시로 int[] arr = {1, 3, 5, 8, 11, 15, 30, 32, 45}이고 key 값이 8인 경우의 이진탐색을 찾는 원리를 확인한다.

while문으로 구성하는 이진 탐색

아래의 예시는 정렬된 배열 arr에서 key 값을 찾는 이진 탐색을 구현한 예시이다.

public class BinarySearchWhile {
    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;

            // target을 찾은 경우
            if (arr[mid] == target) {
                return mid;
            }

            // target이 중간값보다 큰 경우, 왼쪽 절반을 버린다
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                // target이 중간값보다 작은 경우, 오른쪽 절반을 버린다
                right = mid - 1;
            }
        }

        // target을 찾지 못한 경우
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 7;
        int result = binarySearch(arr, target);

        if (result != -1) {
            System.out.println("타겟 값 " + target + "은(는) 인덱스 " + result + "에 있습니다.");
        } else {
            System.out.println("타겟 값을 찾을 수 없습니다.");
        }
    }
}

재귀함수를 이용한 이진 탐색

높은 인덱스가 낮은 인덱스보다 크거나 같은지 확인한다.

public class BinarySearchRecursive {
    public static int binarySearch(int[] arr, int target, int left, int right) {
        if (left > right) {
            // target을 찾지 못한 경우
            return -1;
        }

        int mid = left + (right - left) / 2;

        // target을 찾은 경우
        if (arr[mid] == target) {
            return mid;
        }

        // target이 중간값보다 큰 경우, 오른쪽 절반을 탐색한다
        if (arr[mid] < target) {
            return binarySearch(arr, target, mid + 1, right);
        } else {
            // target이 중간값보다 작은 경우, 왼쪽 절반을 탐색한다
            return binarySearch(arr, target, left, mid - 1);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 7;
        int result = binarySearch(arr, target, 0, arr.length - 1);

        if (result != -1) {
            System.out.println("타겟 값 " + target + "은(는) 인덱스 " + result + "에 있습니다.");
        } else {
            System.out.println("타겟 값을 찾을 수 없습니다.");
        }
    }
}

이진 탐색의 문자열 탐색

---

• 자바의 Collection Framework는 binarySearch를 제공한다.
• list와 찾고자하는 값을 매개변수로 받는다.

⇒ 리스트는 정렬되어있어야 한다.

• 문자열 배열의 경우 이진/이분 탐색을 사용하는 경우 Arrays.binarySearch() 함수를 이용한다.

Arrays.binarySearch()

---

• Arrays.binarySearch() 함수
• → 매개변수로 주어진 배열에서 원하는 값을 이진 탐색하여 인덱스를 반환한다.

public static int binarySearch(Object[] a, Object key)
// Object[] : 탐색하고자 하는 배열
// Object : 배열에서 찾으려는 값

Arrays.binarySearch()를 이용한 이진 탐색 예시

---

• 해당 예시는 String[] 내에서 key 값을 찾고 있다.
• Arrays.binaraySearch() 함수를 이용하여 배열 내에 key 값이 존재하는지 확인

import java.util.Arrays;
/**
 * 이분탐색 : 문자열
 *
 * @param arr {int[]}: 전체 배열
 * @param key {int}: 찾고자 하는 요소
 * @return ResponseEntity<ApiResponse>
 * @link
 * @since 2023.05.
 */@GetMapping("/2")
public ResponseEntity<ApiResponse<Object>> binSearchCourse(@RequestParam String[] arr, @RequestParam String key) {
    int answer = 0;
    Arrays.sort(arr);
    int result = Arrays.binarySearch(arr, key);
    if (result < 0) {
        System.out.println("Element is not present in the array.");
    } else {
        System.out.println("Element is present at index " + result);
    }

    ApiResponse<Object> ar = ApiResponse
            .builder()
            .result(answer)
            .resultCode(SUCCESS_CODE)
            .resultMsg(SUCCESS_MSG).build();
    return new ResponseEntity<>(ar, HttpStatus.OK);
}

Upper Bound 방식과 Lower Bound 방식

• 이분탐색에는 크게 두가지 방식이 존재한다.
• Upper Bound(상한선) 방식과 Lower Bound(하한선) 방식이다.
• Upper Bound방식은 특정 값을 초과하는 첫위치를 반환한다.
• Lower Bound방식은 특정 값 이상인 첫 위치를 반환한다.

• 예를들면, [1, 2, 3, 4, 5, 5, 6, 7 ] 크기가 8인 배열에서 5를 찾고자 할때

Upper Bound 방식은 6의 위치(index = 6)를 반환하고 Lower Bound 방식은 첫번째 5의 위치(index=4)를 반환한다.

• 이 두가지 방식의 구분은 중복 값이 있을 때 중요하다.
• 만약 중복 원소에서 가장 오른쪽 값을 찾으려면 Upper Bound 방식을 통해 구한 값에 -1을 하면 될것이고,
• 중복 원소에서 가장 왼쪽 값을 찾으려면 Lower Bound 방식으로 구한 값 그 자체가 정답이 된다.

---

 

참고 자료

- https://adjh54.tistory.com/187#google_vignette

- https://innovation123.tistory.com/65