[Algorithm] 이분탐색(Binary Search) 알고리즘이란- 개념, 특징, 구현방법

 

 

이분탐색(이진탐색, Binary Search)

출처 - https://wootool.tistory.com/62

 

정의

• 정렬된 자료를 절반씩 쪼개어 탐색하는 방법이다
• 순차탐색보다 빠른 탐색을 위해 나온 방법이다
• 탐색을 진행할 때마다 탐색 범위가 반으로 줄어드므로, 분할 정복 알고리즘의 일종이다
• 데이터가 고정되어 있는 경우에 적합하다
  • 삭제 또는 삽입이 빈번한 경우에는 적합하지 않다

 

 

 

장점

• 시간 복잡도가 O(log N) 으로 빠른 탐색 속도를 갖는다
  • 모든 값을 순차적으로 탐색하는 순차적 탐색방법(O(N))에 비해 시간 복잡도가 낮다

 

 

적용 가능한 경우

 

1. 원소가 정렬되어 있는 경우

• 원소가 정렬된 경우에만 mid 인덱스의 수와의 비교를 통해 탐색 범위를 줄일 수 있다.
• 따라서 오름차순 혹은 내림차순으로 정렬이 되어 있어야만 이분탐색이 가능하다.

 

 

2. 원소의 Random Access가 가능한 경우

• 특정 인덱스의 배열의 값을 O(1)의 시간복잡도로 참조가능해야 한다
• Random Access가 이분탐색에 필수적인 것은 아니지만, Random Access가 가능해야만 이분탐색을 통한 성능 향상을 기대할 수 있다

 

 

방법

 

 

출처 - https://yoongrammer.tistory.com/75

 

• 정렬된 배열(탐색 범위)의 시작(start, left)과 끝(end, right) 인덱스를 구한다.
• 시작과 끝 인덱스의 중간값(mid)을 구해서 찾고자 하는 원소와 비교한다
  • 찾는 원소와 mid 값이 같다면 탐색을 종료한다 
  • 'mid<찾는 원소' 라면 시작 인덱스(start/left)를 mid+1로 하여 다시 탐색한다.
    • start = mid+1
  • 'mid>찾는 원소' 라면 끝 인덱스(end/right)를 mid-1로 하여 다시 탐색한다.
    • end = mid-1
• 끝 인덱스보다 시작 인덱스가 커지게 되면, 찾는 원소가 배열에 존재하지 않는 것이다.

이분 탐색은 재귀(recursion) 또는 반복(iteration)으로 구현할 수 있다. 
둘 중에서는 반복을 통해 구현하는 것이 더 좋다.

 

 

public int binarySearch(int[] arr, int key) {
	int start = 0;
	int end = arr.length;

	while(start <= end) {
		int mid = (start + end) >> 1;
        
		if (arr[mid] == key) {
			return mid;
		} else if (arr[mid] < key){
        	start = mid + 1;
		} else {
			end = mid - 1;
		}
	}

	//못찾았을 때
	return -1;
}

 

 

 

Lower Bound와 UpperBound

 

Lower Bound와 Upper Bound를 사용하는 경우

이분 탐색을 위해서는 mid 인덱스에서의 배열의 값(arr[mid])을 꺼내 찾고자 하는 값과 비교한다.

그리고 그 값이 찾고자 하는 값과 같다면 mid 인덱스를 반환한다.

 

하지만 배열에 같은 값이 중복되어 여러 개 들어가 있다면 어떻게 될까?

여러 요소 중 가장 작은 값을 갖는 인덱스를 반환하거나, 가장 큰 값을 갖는 인덱스를 반환하도록 해야 한다.

가장 작은 값을 갖는 인덱스를 반환하도록 하기 위해서는 Lower Bound를 사용하고

가장 큰 값의 인덱스를 반환하도록 하기 위해서는 Upper Bound를 사용하게 된다.

 

 

 

Lower Bound

일반적인 이분 탐색과는 달리 mid 값이 찾고자 하는 key 값과 같더라도 계속 탐색을 수행한다.

정확히 같은 값을 찾는 일반적인 이분 탐색이 아닌, 처음으로 같은 값이 나오는 인덱스(가장 왼쪽 인덱스)를 찾아야 하기 때문이다.

대신, mid 값이 key 값과 같을 때, start 값은 고정이게 하고 end의 값을 줄이는 방식으로 범위를 줄여 탐색한다.

보통, lower bound를 구하는 문제는 최대의 경우를 구하는 문제이고 start를 반환한다.

public int lowerBound(int[] arr,  int key) {
        int start = 0;
        int end = arr.length;
        
        while (start <= end) {
            int mid = (start + end)/2;
            if (arr[mid] < key) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return start;
}

 

Upper Bound

일반적인 이분 탐색과는 달리 mid 값이 찾고자 하는 key 값과 같더라도 계속 탐색을 수행한다.

대신, mid 값이 key 값과 같을 때, end의 값은 고정이게 하고 start의 값을 증가시키는 방식으로 범위를 줄여 탐색한다.

보통, upper bound를 구하는 문제는 최소의 경우를 구한느 문제이고 end를 반환한다.

public int upperBound(int[] arr,  int key) {
        int start = 0;
        int end = arr.length;
        
        while (start <= end) {
            int mid = (start + end)/2;
            if (arr[mid] > key) {
            	end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return end;
}

 

 

 

이분 탐색 구현시 헷갈리는 경계값 조건

 

while문 조건(탐색 반복 조건)

탐색을 반복하기 위한 while문을 작성할 때, 아래의 세 가지 조건을 선택할 수 있다.

각 세 가지 조건 중 어떤 조건을 사용하냐에 따라 초기 탐색 범위 설정과 이후의 범위 갱신, 반환값 처리 등이 달라진다.

• start + 1< end
• start < end
• start ≤ end

 

시작/끝 인덱스 범위 갱신 

• start + 1< end
  • start와 end 사이에는 반드시 한 개 이상의 원소가 존재하게 된다. 
  • 따라서 start = mid와 end = mid로 범위를 갱신한다(무한 루프를 돌지 않음).
• start < end
  • 이 경우,  start와 end 모두를 mid로 갱신하면 start와 end 사이에 두 개의 원소가 남았을 때 start를 갱신할 수 없다.
  • 즉, 무한루프를 돌게 된다.
  • mid를 (start+end)/2로 계산할 때, 정수 내림 때문에 mid는 start와 같다.
  • 따라서 start = mid + 1, end = mid로 갱신해야만 무한 루프를 돌지 않는다.
• start ≤ end
  • start = end + 1
  • end = mid -1

 

찾고자 하는 값을 반환

이분 탐색이 진행됨에 따라 key값에 가까워지는 것이 무엇인지 생각하고 반환 값을 돌려준다

start == end 일 때까지 루프를 도는 다음의 경우만 살펴보면 찾고자 하는 값에 따라 반환값이 아래와 같이 달라진다.

• start ≤ end
  • 정확히 같은 값(값의 인덱스)을 찾는 경우, mid 반환 
  • lower bound를 찾는다면, start를 반환
  • upper bound를 찾는다면, start 또는 end +1을 반환

 

 

 

참고자료
https://jun-codinghistory.tistory.com/154
https://eine.tistory.com/entry/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89binary-search-%EA%B5%AC%ED%98%84%EC%8B%9C-%EA%B3%A0%EB%A0%A4%ED%95%A0-%EA%B2%83%EB%93%A4
https://wootool.tistory.com/62
https://velog.io/@tomato2532/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89-Lower-Bound-Upper-Bound
https://yoongrammer.tistory.com/75