이진탐색(binary search)

 

1. 배열의 중간값을 확인한다.
2. 찾고자 하는 값이 중간 값보다 작으면 왼쪽 절반을 탐색한다.
3. 찾고자 하는 값이 중간 값보다 크면 오른쪽 절반을 탐색한다.
4. 값을 찾거나 탐색 범위가 없을 때까지 이 과정을 반복한다.

시간 복잡도: O(logn) (효율적)
정렬된 데이터에서만 사용 가능

 

public class BinarySearch {  
    public static int binarySearch(int[] arr, int target){  
        int left = 0;  
        int right = arr.length - 1;  
  
        while(left <= right){  
            // 1 2 3  
            // 1 + (3 - 1) / 2 = 2            // 1 2 3 4            // 1 + (4 - 1) / 2 = 2            int mid = left + (right - left) / 2; // 중간 인덱스 계산  
  
            if(arr[mid] == target){  
                return mid; // 값을 찾음  
            }else if(arr[mid] < target){  
                left = mid + 1; // 오른쪽 절반 탐색  
            }else {  
                right = mid - 1; // 왼쪽 절반 탐색  
            }  
        }  
        return -1; // 값을 찾지 못함  
    }  
  
    public static void main(String[] args) {  
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13};  
        int target = 7;  
  
        int result = binarySearch(sortedArray, target);  
        if(result != -1){  
            System.out.println("값 " + target + "는 인덱스 " + result + "에 있습니다.");  
        }else{  
            System.out.println("값 " + target + "를 찾을 수 없습니다.");  
        }  
    }  
}

 

적용상황
1. 데이터가 정렬된 경우
- 배열이나 리스트에서 값을 찾는 문제
- 로그 파일에서 특정 이벤트를 찾는 경우
2. 특정 조건을 만족하는 값을 효율적으로 탐색할 때
- 특정 범위 내에서 최적의 값을 찾기