이진 탐색

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘

 

*배열이 정렬되어 있어야 한다는 조건이 필요하기 때문에 배열이 정렬되어 있지 않은 경우에는 정렬 작업 필요

 

탐색 범위를 절반씩 줄여나가기 때문에 선형탐색에 비해 빠른 속도를 보장

찾고자 하는 항목의 방향이 정해지면 반대 방향은 탐색할 필요가 없음

 

cf) 선형탐색(Linear Search) 이란?

배열(Array)이나 리스트(List)와 같은 데이터 구조에서 특정한 값을 찾는 알고리즘

 

탐색 과정

배열의 중간 값을 먼저 찾고 해당 값을 찾는 값과 비교

 

중간 값 > 찾는 값일 경우: 왼쪽 부분에서 탐색 진행

중간 값 < 찾는 값일 경우: 오른쪽 부분에서 탐색 진행

(이 과정을 찾는 값이 나올 때까지 반복)

 

Sequential Search는 원하는 값이 나올 때까지 반복하기 때문에 범위를 좁혀나가는 이진탐색에 비해 시간이 오래 걸림

 

사용처

• 데이터의 양이 많을 때
• 데이터가 오름차순으로 정렬되어 있는 상황에서 특정 값을 찾아야 할 때

예시

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

1. low는 첫번째 인덱스, high는 마지막 인덱스를 지정합니다.
2. 마지막 인덱스 보다 첫번째 인덱스가 같아지거나 작을 경우까지 순회합니다.
3. 중간 값을 구합니다.

4.1. 중간 값보다 찾으려는 값(key)가 큰 경우 중간 값에 1을 더하여 오른쪽 절반을 탐색합니다.

4.2. 중간 값보다 찾으려는 값(key)가 작은 경우 중간 값에 1을 빼고 왼쪽 절반만 탐색합니다.

4.3. 이외에 경우 중간 값을 최종값으로 반환합니다.

 

5. 최종 탐색을 못한 경우 값은 -1로 반환합니다.

/**
 * 이분탐색
 *
 * @param arr {int[]}: 전체 배열
 * @param key {int}: 찾고자 하는 요소
 * @return ResponseEntity<ApiResponse>
 * @link
 * @since 2023.05.
 */
@GetMapping("/1")
public ResponseEntity<ApiResponse<Object>> binSearchCourse(@RequestParam int[] arr, @RequestParam int key) {
    int answer = 0;
    // [STEP1] 시작 인덱스와 마지막 인덱스 값을 지정합니다.
    int low = 0;
    int high = arr.length - 1;

    // [STEP2] 마지막 인덱스보다 첫번째 인덱스가 같아지거나 작을 경우까지 순회합니다.
    while (low <= high) {

        // [STEP3] 중간 값을 구합니다.
        int mid = (low + high) / 2;

        // [CASE4-1] 중간 값보다 찾으려는 값(key)가 큰 경우 : 중간 값에 1을 더하여 오른쪽 절반을 탐색합니다.
        if (arr[mid] < key) {
            low = mid + 1;
        }
        // [CASE4-2] 중간 값보다 찾으려는 값(key)가 작은 경우 : 중간값에 1을 빼서 왼쪽 절반을 탐색합니다.
        else if (arr[mid] > key) {
            high = mid - 1;
        }
        // [CASE4-3] 해당 경우가 아니면 중간값을 최종 값으로 반환합니다.
        else {
            answer = mid;
        }
    }
    // [STEP5] 최종 탐색을 하지 못할 경우 -1을 반환합니다.
    if (answer == 0) answer = -1;

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