>  기사  >  Java  >  Java를 사용하여 이진 검색 알고리즘을 구현하는 방법

Java를 사용하여 이진 검색 알고리즘을 구현하는 방법

WBOY
WBOY원래의
2023-09-19 12:57:41840검색

Java를 사용하여 이진 검색 알고리즘을 구현하는 방법

Java에서 이진 검색 알고리즘을 구현하는 방법

이진 검색 알고리즘은 정렬된 배열에 적합한 효율적인 검색 방법입니다. 기본 개념은 검색 범위를 지속적으로 좁혀 검색 값을 배열 중앙의 요소와 비교하고, 대상 요소를 찾을 때까지 비교 결과에 따라 왼쪽 절반 또는 오른쪽 절반을 계속 검색할지 결정하는 것입니다. 검색 범위가 비어 있도록 줄어듭니다.

이제 Java에서 이진 검색 알고리즘을 구현하는 방법을 자세히 소개하겠습니다.

1단계: 이진 검색 방법 구현

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1; //表示未找到目标元素
    }
}

2단계: 이진 검색 방법 테스트

public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; //已排序数组
        int target = 12; //要查找的目标元素
        int index = BinarySearch.binarySearch(arr, target);
        
        if (index != -1) {
            System.out.println("目标元素在数组中的位置为:" + index);
        } else {
            System.out.println("未找到目标元素");
        }
    }
}

위 코드는 먼저 정적 메서드 binarySearchBinarySearch 클래스를 정의합니다. /code>는 이진 검색 알고리즘을 구현하는 데 사용됩니다. binarySearch 메서드에서는 검색 범위의 가장 왼쪽과 가장 오른쪽 요소를 각각 가리키도록 왼쪽오른쪽이라는 두 개의 포인터를 정의합니다. 루프에서는 중간 요소 mid의 인덱스가 계산된 다음 조회 값이 arr[mid]와 비교됩니다. 둘이 동일하면 대상 요소를 찾았으며 해당 요소의 인덱스 값 mid가 반환된다는 의미입니다. 검색 값이 arr[mid]보다 큰 경우 왼쪽 포인터를 오른쪽으로 한 위치 이동하고 검색 범위를 오른쪽 절반으로 좁힙니다. 검색 값이 arr[mid]보다 작은 경우 오른쪽 포인터를 왼쪽으로 한 위치 이동하여 검색 범위를 왼쪽 절반으로 좁힙니다. 대상 요소를 찾거나 검색 범위가 비어 있을 때까지 루프가 계속됩니다. 루프가 끝난 후 대상 요소를 찾을 수 없으면 해당 요소를 찾을 수 없음을 나타내기 위해 -1이 반환됩니다. BinarySearch类,其中包含了一个静态方法binarySearch用于实现二分查找算法。在binarySearch方法中,我们定义了leftright两个指针分别指向查找范围的最左和最右元素。在一个循环中,通过计算得到中间元素的索引mid,然后将查找值与arr[mid]进行比较。如果两者相等,则表示找到了目标元素,返回其索引值mid。如果查找值大于arr[mid],则将left指针右移一位,缩小查找范围为右半部分。如果查找值小于arr[mid],则将right指针左移一位,缩小查找范围为左半部分。循环继续直到找到目标元素或查找范围为空。如果循环结束后未找到目标元素,返回-1表示未找到。

Main类的main方法中,我们创建了一个已排序的数组arr和一个待查找的目标元素target。然后调用BinarySearch类的binarySearch方法进行二分查找,将返回的结果存储在index

Main 클래스의 main 메소드에서 정렬된 배열 arr target. 그런 다음 <code>BinarySearch 클래스의 binarySearch 메서드를 호출하여 이진 검색을 수행하고 반환된 결과를 index 변수에 저장합니다. 마지막으로, 반환된 결과를 바탕으로 대상 요소를 찾았는지 여부를 판단하고 해당 결과를 인쇄합니다.

위의 코드 예제를 통해 Java에서 이진 검색 알고리즘을 구현하는 것은 매우 간단하며 완료하는 데 몇 줄의 코드만 필요하다는 것을 알 수 있습니다. 이 방법의 검색 시간 복잡도는 O(logn)으로 매우 효율적이며 대규모 정렬 배열에 적합합니다. 여러 검색 작업이 필요한 경우 배열의 정렬 작업을 별도로 분할하여 효율성을 높일 수 있습니다.

이 글이 이진 검색 알고리즘을 이해하고 사용하는 데 도움이 되기를 바랍니다! 🎜

위 내용은 Java를 사용하여 이진 검색 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.