[알고리즘] 이진 탐색 개념 + 예제

이진 탐색

💡 이진 탐색은 ‘정렬’ 되어 있는 배열에서 특정 값을 찾는 알고리즘이다.

• 배열의 중간에 있는 임의의 값을 선택하여 찾으려는 대상 값 x와 비교한다.
• x가 중간 값보다 작으면 중간 값을 기준으로 좌측 데이터를 비교
• x가 중간 값보다 크면 배열의 우측 데이터를 대상으로 다시 검색한다.
• 동일한 방법으로 다시 중간 값을 임의로 선택하고 비교한다.

 

이진 탐색 예시

‘55’ 숫자를 찾아본다.

{5, 24, 55, 67, 88, 92, 100}

1️⃣ 첫 번째 시도

먼저 가운데 임의의 값 67을 선택한다.

67 
67 > 55 //두 값을 비교한다.

= 중간 값 67 보다 작으므로 55은 67의 좌측에 존재함을 알 수 있다.

 

2️⃣ 두 번째 시도

{5, 24, 55}

= 67의 좌측 배열 값을 대상으로 2차 이진 탐색을 진행한다.

여기서 가운데 임의의 값은 24.

24
24 < 55 //중앙값 24보다 크다.

= 중간 값 24보다 크므로 55은 24의 우측에 위치함을 알 수 있다.

 

3️⃣ 세 번째 시도

{55}

24을 기준으로 우측 배열을 다시 설정하면, 55 하나만 남아서 원하는 값을 찾을 수 있다.

 

만약 원하는 값을 못 찾는다면?

운 좋게 마지막에 원하는 값을 찾았지만, 원하는 값이 배열에 없다면 어떻게 종료될까?

만약 찾는 값이 40이었다면, 네 번째 시도에서 탐색하고자 하는 배열이 존재하지 않다고 판단하여 그대로 탐색을 종료할 수 있다.

이진 탐색 코드 구현 방법

이진 탐색으로 배열에 접근할 때는 인덱스를 이용한다.

인덱스의 최소 값, 최대 값을 저장하여 탐색이 진행될 때 마다 갱신하고 탐색할 배열의 범위를 줄여나간다.

💡 이진 탐색은 반드시 [정렬되어 있음] 이 사전 조건이다.

// binarySearch(num)
private static boolean binarySearch(int num) {
    int left_index = 0;
    int right_index = n - 1; //n은 배열의 길이이다. 마지막 인덱스는 '배열길이-1'

    //좌측=우측 인덱스가 같아지는 순간까지 이진 탐색을 실행한다.
    while(left <= right) {
            int mid_index = (left_index + right_index) / 2;
            int mid = arr[mid_index]; //배열에서 중앙값을 찾는다.

            //중앙값보다 작다면, 좌측 배열들이 다음 탐색 대상.
            if ( num < mid ) {
                    // 좌측 배열이 대상이다 보니, 좌측 index 는 그대로 유지.
                    // 마지막 right 인덱스만 중앙의 좌측 값 (-1 음수)으로 변경한다. 
                    right_index = mid_index - 1;
            } else if ( num > mid ) {
                    // 우측 배열이 대상이 되어, 우측 index 는 그대로 유지.
                    // 시작하는 left 인덱스만 중앙의 오른쪽 값 (+1 양수)으로 변경한다. 
                    left_index = mid_index + 1;
            }
            else {
                    return true;
            }

            return false; //없는 경우 

    }
}

• 좌측 배열이 대상일때, 좌측 인덱스는 유지 / 우측 인덱스는 중앙 인덱스보다 한 칸 좌측(-1) 으로 변경한다.
• 좌측 배열이 대상일때, 우측 인덱스는 유지 / 좌측 인덱스는 중앙 인덱스보다 한 칸 우측(+1) 으로 변경한다.

 

 

이진 탐색 시간 복잡도

https://backshren20.tistory.com/600

[알고리즘] 빅오 표기법 (big-O)

이진 탐색은 탐색이 진행되면서 처음 n개 크기의 배열의 크기를 반 씩 줄인다고 해서 붙여진 이름이다.

이진 탐색 시간 복잡도는 위에 빅오 표기법을 참조하자!