Interpolation Search 와 Binary Search 의 비교

InterpolationSearch 의 실현 및 Binary Search 와 의 비교
Binary Search 의 실현 에 대해 서 는 여 기 를 볼 수 있 습 니 다.
그러나 위 에서 Binary Search 의 실현 에 대해 저 희 는 재 귀적 호출 방식 으로 이 루어 졌 습 니 다.저희 가 이 두 가지 알고리즘 의 차 이 를 비교 하 는 데 편리 하도록 저 는 Binary Search 를 교체 로 실현 하 겠 습 니 다.코드 는 다음 과 같 습 니 다.

private static int binarySearch(int[] a, int low,int high,int x) {
        int middle;
        while(low<=high){//  ：    “=” 
            middle=low+(high-low)/2;// InterpolationSearch   
            if(a[middle]==x){
                return middle;

            }
            else if(a[middle]>x){
                high=middle-1;

            }
            else{
                low=middle+1;
            }

        }
        return -1;
    }

그리고 InterpolationSearch 의 자바 실현 코드 는 다음 과 같다.

package org.wrh.algorithmimplements;

import java.util.Arrays;
import java.util.Scanner;

//       
public class InterpolationSearch {

    public static void main(String[] args) {
        int []a={10,21,23,42,56,78,98};
        Scanner sc=new Scanner(System.in);
        System.out.print("         ：");
        int x=sc.nextInt();
        int index=interpolation(a,0,a.length-1,x);
        if(index==-1){
            System.out.println("   "+Arrays.toString(a)+" ，    "+x);
        }
        else{
            System.out.println(x+"   "+Arrays.toString(a)+"     ："+index);
        }

    }
/* *          ：low        ，high         ， * * x       */
    private static int interpolation(int[] a, int low,int high,int x) {
        int middle;
        while(low<=high){
            middle=low+(high-low)*(x-a[low])/(a[high]-a[low]);// BinarySearch       ， **  **
            if(a[middle]==x){
                return middle;

            }
            else if(a[middle]>x){
                high=middle-1;

            }
            else{
                low=middle+1;
            }

        }
        return -1;
    }

}

코드 로 볼 때 InterpolationSearch 와 Binary Search 의 유일한 차 이 는 구분 할 때의 중간 값 middle 의 취 법 이 다르다 는 것 입 니 다.Binary Search 에서

middle=low+(high-low)/2;

InterpolationSearch 에 서 는 다음 과 같 습 니 다.

middle=low+(high-low)*(x-a[low])/(a[high]-a[low]);

비교 해 보면 InterpolationSearch 에 서 는 찾 으 려 는 X 의 더 많은 정 보 를 충분히 이용 하여 X 가 배열 에서 의 크기 비례 에 따라 배열 을 구분 하여 검색 속도 가 더욱 빠르다 는 것 을 알 수 있다.
총결산

InterpolationSearch 의 시간 복잡 도 는 O(log(logn)이 고 Binary Search 의 시간 복잡 도 는 O(logn)이기 때문에 정렬 된 배열 을 찾 습 니 다.InterpolationSearch 는 빠 릅 니 다

So why isn’t this used in practice? lg N 은 이미 정말 작 기 때 문 일 수 있 습 니 다.결국,길이 2^32 배열 이 있다 면~32 에서~5 로 떨 어 집 니 다.실 용적 인 용어 로 는 배열 을 검색 하 는 데 큰 속도 가 되 지 않 을 것 입 니 다.참고 하 세 요

마지막 으로 설명 하고 자 하 는 것 은 알고리즘 의 사상 이 여기 서 다른 언어 로 실현 하 는 것 도 매우 쉬 우 므 로 조금 만 바 꾸 면 ok 이다.
수정:위의 while 순환 중

while(low<=high)//   “=” 

이렇게 해야만 배열 서열 중의"0"번 위치 와"length-1"의 위치 요 소 를 정확하게 찾 을 수 있 습 니 다.