이진 탐색 (Binary Search)

이진 탐색 (Binary Search)

 개념

정렬된 데이터에서 특정한 값을 찾아내는 방법

1. 정렬된 데이터의 중간에 위치한 값(Y)을 선택 후, 찾고자 하는 값(X)과 비교

2. 찾고자 하는 값(X)이 선택한 값(Y)보다 작을 경우, 선택한 값(Y)의 좌측 데이터를 탐색

3. 찾고자 하는 값(X)이 선택한 값(Y)보다 클 경우, 선택한 값(Y)의 우측 데이터를 탐색

4. 찾고자 하는 값(X)을 찾기까지 2, 3번의 과정을 계속해서 반복한다.


 시간 복잡도 : T(n) = O(logn)


 Java 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int binarySearch(int[] data, int target, int low, int high) {
    if(low > high)
        return -1;
        
    int middle = (low + high)/2;
    
    if(target == data[middle])
        return middle;
    
    else if(target < data[middle])
        return binarySearch(data, target, low, middle - 1);
    
    else
        return binarySearch(data, target, middle + 1, high);
}
cs


 코드 해석

✓ data = { 17, 23, 39, 44, 56, 63, 77 }

   위와 같이 크기가 7인 정렬된 배열의 예시가 있다.

✓ low는 배열의 첫 번째 인덱스의 값인 0, high는 배열의 마지막 인덱스 값인 6이다. (low = 0, high = 6)

           (배열의 인덱스는 0부터 시작한다.)

target은 찾고자 하는 값이므로 17를 예로 든다. (target = 17)


▪︎ 첫 번째 탐색

▫︎ (2번 라인) if(low > high) 결과 값이 (0 < 6)이므로 조건 불일치

▫︎ (5번 라인) middle = 3

▫︎ (7번 라인) if(target == data[3]) 결과 값이 (17 < 44)이므로 조건 불일치

▫︎ (10번 라인) else if(target < data[3]) 결과 값이 (17 < 44)이므로 조건 일치

☛ { 17 } < { 17, 23, 39, 44 } { 56, 63, 77 }

재귀 함수 실행 : binarySearch(data, target, low, middle-1) ☛ binarySearch(data, 0, 2)


▪︎ 두 번째 탐색

▫︎ (2번 라인) if(low > high) 결과 값이 (0 < 2)이므로 조건 불일치

▫︎ (5번 라인) middle = 1

▫︎ (7번 라인) if(target == data[1]) 결과 값이 (17 < 23)이므로 조건 불일치

▫︎ (10번 라인) else if(target < data[1]) 결과 값이 (17 < 23)이므로 조건 일치

☛ { 17 } < { 17, 23} { 39, 44 } { 56, 63, 77 }

재귀 함수 실행 : binarySearch(data, target, low, middle-1) ☛ binarySearch(data, 0, 0)


▪︎ 세 번째 탐색

▫︎ (2번 라인) if(low > high) 결과 값이 (0 = 0)이므로 조건 불일치

▫︎ (5번 라인) middle = 0

▫︎ (7번 라인) if(target == data[0]) 결과 값이 (17 == 17)이므로 조건 일치

☛ { 17 } = { 17 } { 23 } { 39, 44} { 56, 63, 77 }

▫︎ (8번 라인) middle의 값 0을 반환 후 종료


 코드 결과

세 번째 탐색까지 끝내고 출력되는 값은 0이다.

재귀 함수를 이용해서 전체 데이터에서 중간의 데이터를 탐색 후 비교하고,

값이 작으면 중간 데이터 기준으로 왼쪽에 위치한 전체 데이터에서 다시 중간의 데이터를 탐색하는 방법이다.

(배열에서 찾은 데이터의 위치를 반환하는 메서드)




✔︎ 오타, 틀린 개념이 있을 경우 댓글 달아주세요~!

(확인 수정하도록 하겠습니다~^^)


✔︎ 추가할 개념이 있다면 댓글 부탁드립니다~!

(지식을 공유해주세요~^^)

댓글