Java의 이진 검색: 재귀, 반복 및 Java 컬렉션

Java의 선형 검색은 항상 배열에서 요소를 찾는 방법이었습니다. 배열의 각 요소를 순차적으로 검색하며 구현하기가 매우 쉽습니다. 그러나 선형 검색의 단점은 문제의 배열에 수만 개의 요소가 포함되어 있을 때 명백합니다. 이러한 경우 이진 검색에 의해 구현된 "분할 및 정복" 방법은 시간 및 공간 복잡성을 염두에 둔 프로그래머에게 훨씬 더 효율적이고 바람직합니다.

이진 검색

이진 검색에서는 키(검색 중인 요소)를 찾을 때까지 배열을 두 부분으로 반복해서 나눕니다. 분할은 가상입니다. 즉, 데이터의 무결성이 유지됩니다. 반복할 때마다 배열의 중간 값에 초점이 맞춰집니다. 값이 찾고 있는 키와 같으면 루프 또는 재귀 함수가 종료됩니다. 그렇지 않으면 계속 반복됩니다. 가운데 값이 키보다 크면 함수는 배열의 전반부에 초점을 맞추고 그 반대도 마찬가지입니다. 이 프로세스는 키를 찾거나 전체 배열이 반복될 때까지 반복됩니다.

선형 검색과 이진 검색의 차이점

이진 검색 알고리즘

이진 검색 알고리즘은 다음과 같습니다.

1. 배열의 첫 번째 지점과 마지막 지점을 결정합니다. 포인트는 배열 및 검색 중인 키에 따라 각 반복에서 조정됩니다.
2. 배열을 반복하고 현재 첫 번째 포인트와 마지막 포인트 사이의 중간 값을 비교합니다. 첫 번째 반복에서 첫 번째 변수와 마지막 변수는 배열의 실제 변수와 동일합니다.
3. 키가 중간 값보다 크면 해당 값의 인덱스가 새로운 "First" 변수에 저장됩니다.
4. 키가 중간 값보다 작은 경우 해당 값의 인덱스가 'Last' 변수에 저장됩니다.
5. 이 조건은 다음 두 조건 중 하나가 참이 될 때까지 반복됩니다.
   • 열쇠가 발견되었습니다.
   • 전체 배열이 반복되었습니다.

반복 이진 검색 및 재귀 이진 검색에 대한 코드는 다음과 같습니다.

반복 이진 검색

반복 방법을 사용한 이진 검색 코드는 다음과 같습니다.

import java.util.Scanner;
public class IterativeBinarySearch {

    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};

        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);

        int num = input.nextInt();
        int result = BinarySearchIterative(arr,num);

        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }

    public static int BinarySearchIterative(int[] arr, int num){
        //Representing the Start and End Index After Division of Array
        int start = 0;
        int end = arr.length;

        //Loop to Iterate Through the Array
        for(int i = 0; iarr[n]){
                start = n;
            }
            //If number to search for is greater than the arr value at index 'n'
            else{
                end = n;
            }
        }
        //If number isn't found, return -1
        return -1;
    }
}

재귀 이진 검색

재귀를 사용하는 이진 코드는 다음과 같습니다.

import java.util.Scanner;
public class RecursiveBinarySearch {

    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};

        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);

        int num = input.nextInt();
        int result = BinarySearchRecursive(arr,0,arr.length-1,num);

        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }

public static int BinarySearchRecursive(int arr[], int a, int b, int num){
    //Base Case to Exit the Recursive Function
    if (b < 1) {
        return -1;
    }
        int n = a + (b=1)/2;

       //If number is found at mean index of start and end
        if(arr[n]==num)
            return n;

       //If number to search for is greater than the arr value at index 'n'
        else if(arr[n]>num)
            return BinarySearchRecursive(arr,a,n-1,num);

       //If number to search for is greater than the arr value at index 'n'
        else
            return BinarySearchRecursive(arr,n+1,b,num);
    }

}

시간 복잡도

통과하는 반복마다 배열, 즉 검색 공간이 반으로 나뉩니다. 매 반복 'm' 후에 검색 공간은 N/2m 크기로 변경됩니다. 최악의 시나리오에서는 배열의 반대쪽에 하나의 요소만 남게 됩니다. 이때 이진 검색의 복잡도는 k = log2N이 됩니다. 선형 검색의 시간 복잡도는 O(N)이므로 이진 검색이 O(log2N) 복잡도로 훨씬 빨라집니다. 이것이 선형 검색보다 이진 검색을 사용하는 주요 이점입니다.

공간 복잡성

이진 검색은 start, end 및 mid의 세 가지 변수를 사용합니다. 이 세 변수는 배열 인덱스의 메모리 위치를 가리키는 포인터로 생성됩니다. 이로 인해 이진 검색은 공간에 대해 매우 효율적입니다. 반복 이진 검색의 공간 복잡도는 O(1)입니다. 재귀 구현의 경우 O(log N)입니다.