Arrays.binarySearch() 방법

Arrays.binary Search () 방법은 질서정연한 수조에서 특정한 대상의 위치를 찾는 데 사용되며, 그 대상 수조는Comparable 인터페이스를 실현해야 하며, 그렇지 않으면java를 잘못 보고할 수 있습니다.lang.ClassCastException 은 두 가지 예를 들어 검증합니다.
먼저 기본 int 배열 형식:

public static void testIntSearch() {
	int[] array = new int[10];
	Random random = new Random(47);
	for (int i = 0; i < array.length; i++) {
		array[i] = random.nextInt(30);
	}
	// array[0] 
	int flag = array[0];
	System.out.println(" array:" + Arrays.toString(array));
	Arrays.sort(array);
	System.out.println(" array:" + Arrays.toString(array));
	System.out.println("array[0]=" + flag + ", :" + Arrays.binarySearch(array, flag));
	System.out.println("2 :" + Arrays.binarySearch(array, 2));
	System.out.println("-10 :" + Arrays.binarySearch(array, -10));
	System.out.println("100 :" + Arrays.binarySearch(array,100));
}

출력: 정렬 전array: [8, 5, 13, 11, 1, 29, 28, 20, 12, 7]
순서 다음array:[1,5,7,8,11,12,13,20,28,29]
array[0]=8, 정렬 후 위치: 3
2 배열의 위치: -2
-10 배열의 위치: -1
100 배열의 위치:-11
배열은 Random에서 생성되었지만 Random 구성 매개 변수 seed가 지정한 후random.nextInt(30) 매번 생성된 숫자는 이때 무작위 숫자가 아니다. 즉,array 수조가 생성될 때 매번 똑같다는 것이다.flag로 array[0]의 값을 기록한 다음 정렬된 flag의 위치를 확인합니다.출력에서flag=8을 알고 정렬한 후 수조에 있는 위치는 3이다. 즉, 정렬한 후flag=array[3]이다.만약에 수조에 존재하지 않는 숫자를 조회하면 2는 -2로 되돌아간다. 이 값은 정렬 규칙에 따라 삽입점이 결정되고 삽입점의 위치가 index라고 가정하면 되돌아오는 값은 -(index+1)이다.만약 삽입점이 수조의 맨 처음 부분에 있다면 -1로 통일된다.삽입점이 수조의 끝에 있으면 수조의 길이와 관련이 있고 수조의 길이가length라고 가정하면 -(length+1)로 되돌아온다.
위의 검증은 int형의 수조를 사용하고, 아래는 일반적인 대상형의 수조를 사용한다

public static class E23 implements Comparable {
		private int value;

		public E23(int value) {
			this.value = value;
		}

		@Override
		public String toString() {
			return value + "";
		}

		@Override
		public int compareTo(E23 o) {
			if (this.value > o.value) {
				return 1;
			} else if (this.value < o.value) {
				return -1;
			} else {
				return 0;
			}
		}
		
		public static void main(String[] args) {
			E23[] a = new E23[10];
			Random random = new Random();
			for (int i = 0; i < a.length; i++) {
				a[i] = new E23(random.nextInt(10));
			}
			E23 e23 = a[0];
			System.out.println(Arrays.toString(a));
			Arrays.sort(a);
			System.out.println(Arrays.toString(a));
			System.out.println(e23.value + " :" + Arrays.binarySearch(a, e23));
		}
	}

처음에 Comparable를 계승하지 않았기 때문에 타임즈에 이상이 생겼습니다. 이상에 의하면 Comparable 인터페이스를 계승해야 한다고 추측했습니다. 여기서 깊이 연구하지 않았습니다. 원인은 뒤에 있는 원본에 대한 설명입니다.E23은 간단한 클래스로private의 int역 파라미터가 있고Comparable 인터페이스를 계승하여comparaTo를 실현하는 방법이 있습니다. 여기는 int역의 크기를 비교하는 데 사용됩니다. 여기는 반드시 세 가지 상황의 값을 되돌려야 합니다. 작음과 같음은 0보다 크고 다른 두 가지 상황은 정해진 정렬 순서에 따라 되돌려야 합니다.결과에서 알 수 있듯이 대상 유형의 정렬 후의 수조도 찾을 수 있으며 그 결과는 기초 유형과 같다.
다음은 Arrays를 살펴보겠습니다.binary Search () 방법의 원본: 여기에 사용되는 것은 binary Search (int [] a, int key) 와 binary Search (T[] a, T key) 입니다. 일반 유형의 binary Search (T[] a, T key) 방법을 살펴보겠습니다.

public static int binarySearch(Object[] a, Object key) {
        return binarySearch0(a, 0, a.length, key);
    }

그 밑바닥은 사실binarySearch0(a,0,a.length,key) 방법입니다. 이 방법을 계속 보십시오.
4

private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
                                     Object key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            @SuppressWarnings("rawtypes")
            Comparable midVal = (Comparable)a[mid];
            @SuppressWarnings("unchecked")
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

이 방법은 원소를 찾는 가장 기본적인 알고리즘이 실현되었을 것이다.fromIndex와 toIndex를 지정하지 않았기 때문에 기본적으로 전체 수조 검색을 한다.while 순환에서 이분법의 알고리즘을 사용하여 요소가 수조에 있는 위치를 찾는다.while에서 첫 번째 줄은 이분 후 구역의 중간 위치를 찾는다는 뜻이다.다음 코드는 왜 Comparable를 계승해야 하는지를 설명한다.Comparable를 계승하지 않으면 유형 전환 오류의 이상을 보고할 것이다.다음에 compareTo 방법을 사용해서 비교해 보면 왜 이 방법은 정렬 후의 수조에만 사용할 수 있는지 알 수 있다. 이곳의 이분법은 수조가 질서정연하다는 전제하에 세워진 것이고 순서가 없으면 여러 가지 상황이 발생할 수 있다.