이진 검색 (Binary Search) 알고리즘 Java

이진 검색 알고리즘은 Java 정렬된 배열 내에서 특정 값을 찾는 데 사용되는 효율적인 프로그래밍 방법입니다. 이 접근 방식은 배열을 지속적으로 두 부분으로 나누고 검색 값을 중간 요소와 비교합니다.

이진 검색 알고리즘의 작동 방식

이진 검색 알고리즘은 검색 값을 배열의 중간 요소와 비교하는 것으로 시작됩니다. 검색 값이 중간 요소와 같으면 알고리즘은 해당 요소의 위치를 ​​반환합니다. 검색 값이 중간 요소보다 작으면 알고리즘은 배열의 왼쪽 절반에서 검색을 계속합니다. 검색 값이 더 크면 알고리즘은 배열의 오른쪽 절반에서 검색을 계속합니다. 이 프로세스는 검색 값을 찾거나 검색할 요소가 더 이상 없을 때까지 반복됩니다.

이진 검색 알고리즘의 장점과 단점

장점:

• 고효율: 이 알고리즘은 각 단계에서 요소의 절반을 제거하여 대규모 배열 검색을 최적화합니다.
• 낮은 시간 복잡도: 이 알고리즘의 시간 복잡도는 O(log n)이므로 대규모 데이터 세트에 효과적입니다.

단점:

• 정렬된 배열 요구 사항: 알고리즘은 정렬된 배열에서만 작동합니다.

예와 설명

의 정렬된 정수 배열에서 특정 정수를 찾기 위해 이진 검색 알고리즘을 사용하는 예를 생각해 보세요 Java.

public class BinarySearchExample {  
    public static int binarySearch(int[] array, int target) {  
        int left = 0;  
        int right = array.length- 1;  
  
        while(left <= right) {  
            int mid = left +(right- left) / 2;  
  
            if(array[mid] == target) {  
                return mid; // Return position if found  
            } else if(array[mid] < target) {  
                left = mid + 1;  
            } else {  
                right = mid- 1;  
            }  
        }  
        return -1; // Return -1 if not found  
    }  
  
    public static void main(String[] args) {  
        int[] numbers = { 1, 3, 5, 7, 9, 11, 13, 15 };  
        int target = 9;  
  
        int position = binarySearch(numbers, target);  
  
        if(position != -1) {  
            System.out.println("Element " + target + " found at position " + position);  
        } else {  
            System.out.println("Element " + target + " not found in the array");  
        }  
    }  
}  

이 예에서는 이진 검색 알고리즘을 사용하여 정렬된 정수 배열에서 숫자 9를 찾습니다. 알고리즘은 배열을 반복하고 검색 값을 중간 값과 비교합니다. 이 경우 숫자 9는 배열의 위치 4(0부터 시작하는 인덱스)에 있습니다.

Java 이 예에서는 이진 검색 알고리즘이 정렬된 정수 배열에서 요소를 찾는 방법을 보여 주지만 프로그래밍 의 다른 검색 시나리오에도 적용할 수 있습니다 .