이분 탐색(Binary Search)

이분 탐색이란 정렬된 배열 혹은 리스트에서 데이터를 빠르게 탐색할 수 있는 방법으로, 배열 내부의 데이터가 정렬되어 있어야만 사용이 가능합니다. 배열의 중앙에 있는 값을 보고, 찾고자 하는 데이터가 왼쪽 혹은 오른쪽 부분에 있는지를 파악하여 탐색의 범위를 반으로(O(logN)) 줄여가는 방식을 반복적으로 사용하여 데이터를 탐색합니다.

 

 

이분 탐색은 주로 언제 사용하는가?

 

이는 데이터의 삽입 혹은 삭제가 빈번할 경우엔 적합하지 않으며, 주로 고정된 데이터에 대한 탐색에 적합합니다. 또한 

다량의 데이터를 검색하거나 탐색 범위가 1,000만 단위 이상으로 넘어가면 이분 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 문제 해결에 도움이 될 것입니다.

 

이분 탐색은 아래와 같이 위치를 나타내는 변수 3개를 사용하여, 찾고자 하는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교합니다.

• 탐색하고자 하는 범위의 시작점 = 0 = Start
• 탐색하고자 하는 범위의 끝점 = 배열의 길이 - 1 = End
• 탐색하고자 하는 범위의 중간점 = (Start + End) / 2 = Mid

 

다음과 같은 3가지 아이디어를 기억합시다. (오름차순 기준)

 

1) 찾고자 하는 데이터 값이 배열[Mid] 값보다 큰 경우, Start 값을 증가시킵니다.

→ Start = Mid + 1

2) 찾고자 하는 데이터 값이 배열[Mid] 값보다 작은 경우, End 값을 감소시킵니다.

→ End = Mid - 1

3) 찾고자 하는 데이터 값이 배열[Mid]에 위치한 경우, Mid를 반환합니다.

→ Mid !

 

💻 이분 탐색 구현(JAVA)

1. 반복문으로 구현

public static boolean BinarySearch(int[] arr, int n) {
	int start = 0;
    int end = arr.length - 1;
    int mid;
    
    while(left <= right) {
    	mid = (start + end) / 2;
        if(arr[mid] < n) end = mid - 1;
        else if(arr[mid] > n) start = mid + 1;
        else return true;
    }
    return false;
 }

2. 재귀로 구현

public static boolean BinarySearch(int[] arr, int n, int start, int end) {
	if(start > end) return false;
    
    int mid = (start + end) / 2;
    
    if(arr[mid] < n) 
    	return BinarySearch(arr, n, arr[mid] + 1, end)
    else if(arr[mid] > n)
    	return BinarySearch(arr, n, start, arr[mid] - 1)
    else
    	return true;
}

 

하나 주의할 점은, Mid의 기준을 출제자의 의도를 파악하여 적절히 설정할 수 있어야 합니다. 보통 배열의 인덱스로 설정하지만 난이도가 있다면 꼭 인덱스만이 Mid의 기준이 되는 것은 아닙니다.

---

References

https://minhamina.tistory.com/127

https://bbangson.tistory.com/73