[Algorithm/Java] 이분 탐색(Binary Search)

🔎 이분 탐색이란?

이분 탐색은 이진 탐색, Binary Search 라고도 한다. 순차적 탐색보다 빠른 탐색을 위해 나온 방법으로 실제로 이분탐색의 시간복잡도는 순차적 탐색보다 낮다. 

 

순차적 탐색 

• 정렬된 배열 내에서 특정 원소를 찾기 위해 0번 인덱스부터 차례로 탐색 
• 원소를 건너뛰는 일 없이 순차적으로 모두 탐색 

 

이분 탐색

• 정렬된 배열 내에서 특정 원소를 찾을 때 인덱스 i부터 j의 중간값과 비교 
• 중간값이 찾는 원소가 아니라면, 인덱스 i와 j를 다시 정해줌 
• 인덱스 i와 j의 범위는 정할 때 마다 탐색 범위의 반으로 줄어듦 

 

 

이분 탐색 방법

1. 처음 탐색 범위는 인덱스 0부터 끝까지이다. 해당 범위의 중간 인덱스를 mid로 둔다. 

 

2. mid와 찾는 원소의 값을 비교한다. 

• 찾는 원소와 mid 값이 같다면 탐색 종료 
• mid 값 < 찾는 원소 라면, left 를 mid+1로 하여 다시 2번 과정을 반복한다. 
• mid 값 > 찾는 원소 라면, right를 mid-1로 하여 다시 2번 과정을 반복한다.

 

3. 만약 right > left 가 된다면 해당 배열에 찾는 원소가 없는 것이다. 

 

 

이분 탐색 구현 (Java) 

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

 

---

시간 복잡도 비교

• 순차적 탐색 : 최악의 경우 배열의 끝까지 탐색해야 한다. → O(n) 
• 이분 탐색 : 범위를 새로 정할 때마다 탐색 범위는 절반으로 줄어든다. → O(log n)