Java에서 이진 검색을 구현하는 기본 방법(코드 포함)

이 글의 내용은 Java에서 (코드 포함) 바이너리 검색을 구현하는 기본 방법에 대한 것입니다. 필요한 친구들이 참고할 수 있기를 바랍니다.

이진 검색은 특히 이해하기 쉽습니다. 이는 빠른 정렬 및 병합에서 사용되는 분할 정복 개념과 유사합니다. 매번 중간 숫자를 대상 숫자와 비교한 다음입니다. 간격이 더 큰지 작은지 결정됩니다.

예:

샤오홍은 1~100(이 숫자는 56) 중에서 숫자를 선택하고 샤오밍에게 추측을 요청하여 다음과 같은 대화가 나왔습니다. #🎜 🎜 #

Xiao Ming의 첫 번째 추측: 68

small红: 크다

Xiao Ming의 두 번째 추측: 35

작은红: 작음

Xiao Ming의 세 번째 추측: 58

Xiaohong: Big

Xiao Ming의 네 번째 추측: 49

작은红:小了

Xiao Ming의 다섯 번째 추측: 54

小红：小了

Xiao Ming의 여섯 번째 추측 :56

#🎜🎜 #샤오홍: 빙고! ! !

위 대화에서 Xiao Ming은 답이 맞을 때까지 추측할 때마다 간격을 좁힐 수 있음을 알 수 있습니다

이진 검색은 다음과 같습니다. 이제 배열 8, 11, 19, 23, 27, 33, 45, 55, 67, 98이 있고 아래와 같이 이진 검색을 사용합니다.

은 각각 간격의 절반을 줄일 수 있습니다. 시간에 따라 간격이 다음과 같이 변경되는 것을 볼 수 있습니다.

간격 크기가 무한히 1에 가까울 때 k = log2n이므로 시간 복잡도는 다음과 같습니다. 오(로그인).

특히 이해하기 쉽지 않나요? 다음은 제가 Java로 구현한 간단한 이진 검색입니다(참고: 이는 가장 간단한 구현이며 이진 검색의 변형은 매우 복잡하며 저는 아직 아직 마스터했습니다)

package com.structure.search;

/**
 * 二分查找法
 *
 * @author zhangxingrui
 * @create 2019-02-15 21:29
 **/
public class BinarySearch {

    public static void main(String[] args) {
        int[] nums = new int[]{4, 6, 9, 19, 30, 40, 500, 3450, 50004, 4334343};
        System.out.println(binarySearch(nums, 0, nums.length - 1, 30));
        System.out.println(binarySearch(nums, 50004));
    }

    /**
     * @Author: xingrui
     * @Description: 二分查找法（针对有序数组且不存在重复元素-递归方式实现）
     * @Date: 21:37 2019/2/15
     */
    private static int binarySearch(int[] nums, int p, int r, int k){
        if(p > r)
            return -1;

        int mid = (p + r) / 2;
        if(nums[mid] == k)
            return mid;

        if(k > nums[mid])
            return binarySearch(nums, mid + 1, r, k);
        else
            return binarySearch(nums, p,  mid - 1, k);
    }

    /**
     * @Author: xingrui
     * @Description: 二分查找法（针对有序数组且不存在重复元素-循环实现）
     * @Date: 21:37 2019/2/15
     */
    private static int binarySearch(int[] nums, int k){
        int p = 0;
        int r = nums.length - 1;
        while (p <= r){
            int mid = (p + r) / 2;

            if(nums[mid] == k)
                return mid;

            if(k > nums[p])
                p = mid + 1;
            else
                r = mid - 1;
        }
        return -1;
    }

}

코드는 매우 간단하며, 주목해야 할 것은 경계 조건 p<=r입니다.

간단한 구현에는 큰 한계가 있으며 중복된 데이터가 없는 정렬된 배열에만 적용할 수 있다는 것도 코드에서 알 수 있습니다.

또한 이진 검색은 소규모 데이터 쿼리에 적합하지 않으며(소규모 데이터 쿼리가 필요하지 않기 때문에) 동시에 이해하기 쉬우며 대규모 쿼리에는 적합하지 않습니다. -규모 데이터 쿼리, 그 이유는 무엇입니까?

위에서 언급한 이유는 이진 검색은 배열을 사용하는 기본 데이터에 적합하지만 배열은 연속적인 메모리 공간이므로 데이터가 클 경우 이진 검색을 사용하려는 경우입니다. 데이터 기본 구현

은 배열만 사용할 수 있는데 이는 좋지 않습니다. 내 데이터에 G가 있다고 가정하면 1G의 연속 메모리 공간을 신청해야 합니다. 맙소사, 꽉 차버릴까봐 두렵습니다.

위 내용은 Java에서 이진 검색을 구현하는 기본 방법(코드 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!