이진 탐색 (Binary Search)

 

 

 

이진 탐색이란?

 

이진 탐색이란 정렬되어 있는 데이터에서 특정한 값을 찾아내는 알고리즘이다.

 

• 이진 탐색은 탐색 범위를 반으로 나누어 찾는 값을 포함하는 범위를 좁혀가는 방식이다. 주로 배열의 인덱스를 기준으로 배열 내의 값을 탐색하는 데 사용되고, 리스트, 트리 등에서도 사용한다.
• 일정한 순서로로 정렬된 구조에서만 사용할 수 있기 떄문에 정렬된 리스트나 트리에서 사용할 수 있다
  
  
• 이진 탐색의 시간 복잡도는 O(log n)으로 배열의 크기에 비례하여 실행 시간이 빨라진다.

 

-> 대용량 데이터에서 특정 값의 위치를 찾는 데 용이하다.

 

 

 

 

이진 탐색의 동작 방식

1. 정렬된 배열에서 중간 인덱스를 찾는다.
2. 찾으려는 값과 중간 값을 비교한다.
3. 찾으려는 값이 중간 값보다 작으면 왼쪽 부분 배열을 크면 오른쪽 부분 배열을 탐색한다.
4. 탐색 범위를 반으로 줄인다.
5. 더 이상 탐색할 값이 없을 때까지 위 과정을 반복한다.

 

 

public class BinarySearch {
    stsatic int[] arr = {1, 3, 5, 7, 8, 10, 22, 37, 57, 88};
    
    public static void main(String[] args) {
        System.out.println(binarySearch1(5, 0, arr.length-1));  // 2
        System.out.println(binarySearch2(22, 0, arr.length-1)); // 6
    }
    
    // 재귀적 탐색
    static int binarySearch1(int key, int low, int high) {
        int mid;
        
        if(low <= high) {
            mid = (low + high) / 2;
            
            if(key == arr[mid]) { // 탐색 성공
                return mid;
            } else if (key < arr[mid]) {
                return binarySearch1(key, low, mid-1); // 왼쪽 부분
            } else {
                return binarySearch1(key, mid+1, high); // 오른쪽 부분
            }
        }
        
        return -1; // 탐색 실패
    }
    
    // 반복적 탐색
    static int binarySearch2(int key, int low, int high) {
        int mid;
        
        while(low <= high) {
            mid = (low + high) / 2;
            
            if (key == arr[mid]) {
                return mid;
            } else if (key < arr[mid] {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        
        return -1; // 탐색 실패
    }
}