이분법 검색을 구현하십시오
이진 검색 방법은 배열에서 순서 시퀀스가 필요합니다. 이진 검색은 선형 검색 이상입니다. 배열이 더 많을수록 효율성이 더 명백합니다. 이진 검색의 효율은 다음과 같습니다. O (log2n) n은 2의 m 전력 범위에 있으므로 최대 검색 수는 M입니다. log2n은 2의 m 전력이 n과 같고, 상수를 생략하고, o (logn)로 약어를 의미합니다.
200 개의 요소가 주문 된 배열이있는 경우 최대 이진 검색 수가 있습니다.
2^7 = 128, 2^8 = 256, 7의 전력이 200에 도달 할 수없고 8의 전력에는 포함되므로 최대 검색 수는 8입니다.
// 루프, 바이너리 검색 정적 int binarySearch (int [] array, int data) {int start = 0; int end = array.length -1; int mid = -1; while (start <= end) {system.out.println ( "검색 수"); mid = (시작 + 끝) >>> 1; if (array [mid] <data) {start = mid + 1; } else if (array [mid]> data) {end = mid -1; } else {리턴 중간; } system.out.println ( "start ="+start+", end ="+end+", mid ="+mid); } 반환 -1; } // 재귀 바이너리 검색 초기 시작 = 0, end = array.length -1 static int biniorsearch4recursion (int [] array, int data, int start, int end) {int mid = -1; System.out.println ( "검색 수"); if (start> end) {리턴 중간; } mid = (start + end) >>> 1; if (array [mid] <data) {return binarysearch4recursion (array, data, mid + 1, end); } else if (array [mid]> data) {return binarysearch4recursion (배열, 데이터, 시작, 중간); } else {리턴 중간; }}이분법적인 삽입 정렬
시퀀스 a [0], a [1] ... a [n]; [i-1]이 이미 주문한 곳. [i]를 삽입 할 때 이분법을 사용하여 [i] 삽입 효율의 위치를 검색하십시오 : O (n^2). 기본적으로 정렬 된 시퀀스의 경우 효율은 직접 삽입 분류만큼 좋지 않습니다. 무작위 및 무질서한 서열의 경우 효율은 직접 삽입 분류보다 높습니다.
/** 양파 (접힌 및 반) 삽입 정렬* 시퀀스 a [0], a [1] ... a [n]; [i-1]이 이미 주문한 곳. [i]가 삽입되면 이분법을 사용하여 [i] 삽입*/ public class binaryinsertsort {public static void main (string [] args) {int len = 10; int [] ary = new int [len]; 랜덤 random = new random (); for (int j = 0; j <len; j ++) {ary [j] = random.nextint (1000); } binaryInsert (ary); / * * 복잡성 분석 : 최선의 경우, 즉, 모두 정렬되었으므로 바로 움직일 필요가 없습니다. 이 시점에서 시간 복잡성은 다음과 같습니다. O (n lg n) 최악의 경우는 모든 역 순서이며,이 시점에서 복잡성은 O (n^2) * 최악의 경우의 복잡성을 O (n | logn)로 향상시킬 수 없습니다. */ // 배열 인쇄 프로그램 (Ary); } / *** 삽입 정렬* @param ary* / private static void binaryInsert (int [] ary) {int setValuecount = 0; // 첫 번째 요소 자체가 (int j = 1; j <ary.length; j ++)를 정렬해야하기 때문에 배열의 두 번째 요소에서 정렬합니다. {// complexity n // 현재 값을 저장 int key = ary [j]; // ∆ 이진 검색을 사용하여 삽입 위치를 찾으려면 // int index = binarysearchasc (ary, ary [j], 0, j -1); // 복잡성 : o (logn) // int index = binarysearchdesc (ary, ary [j], 0, j -1); // 복잡성 : o (logn) intincearchdesc2 (ary, j], j) 1); // 복잡성 : O (logn) printArray (ary); System.out.println ( "" +j +"인덱스 위치에 삽입 할 인덱스 :" +index); // 대상을 위치에 삽입하고 (int i = j; i> index; i-) {// 복잡성, 최악의 경우 : (n-1)+(n-2)+...+n/2 = o (n^2) ary [i] = ary [i-1]; // i-1 <==> index setValueCount ++; } ary [index] = 키; setValuecount ++; } system.out.println ( "/n 값 수 (setValueCount) =====>" + setValueCount); } / *** 바이너리 검색 오름차순 재귀** @param a ary* @param target* @param target* @param을 찾으십시오* @param* @param에서* @param에서* @return* @return* @return은 순서* / private static int binarys searchasc (int to)에 있어야합니다. {int range = to -from; // 범위가 0보다 크면, 즉, 두 개 이상의 요소가 있으면 (범위> 0) {// 중간 비트 int mid = (to + from) / 2; // 임계 비트가 충족되지 않으면 (ary [mid]> target) {/ * * mid> target, 오름차순 규칙, 대상이 작고 대상이 작고, 위치가 스왑되어야하는 경우, 대상은 검색 아이디어에 따라 순서대로 고려되므로 = 중간에 고려됩니다. } else { / * * MID <대상, 오름차순 규칙, 대상이 크며 위치가 교환되지 않습니다. 비교를 검색하기위한 시작 위치는 MID + 1 */ return binarySearchasc (Ary, Target, Mid + 1,)이어야합니다. }} else {if (ary [from]> target) {// 예를 들어, 5,4, 삽입 할 것은 4에서 4입니다. } else { + 1에서 반환; }}} / *** 바이너리 검색 내림차순 순서, 재귀* / 개인 정적 int binarysearchdesc (int [] ary, int target, int from, int to) {int range = to -from; if (range> 0) {int mid = ( + ~) >>> 1; if (ary [mid]> target) {return binarysearchdesc (ary, target, mid + 1,); } else {return binarySearchDesc (ary, target, from, mid -1); }} else {if (ary [from]> target) {// 예를 들어, 5,4, 삽입해야 할 것은 4 + 1에서 4입니다. } else {return from; }}} / *** 바이너리 검색 내림차순 순서, 비 재구성* / 개인 정적 int binarySearchDesc2 (int [] ary, int target, int tog, int to, int to, int to) {// while (from <to) {int mid = (from + to) >>> 1; if (ary [mid]> target) {from = mid + 1; } else {to = mid -1; }} //에서 <==>로; if (ary [from]> target) {// 5,4 인 경우 삽입 할 것은 + 1에서 4 리턴입니다. } else {return from; }} private static void printArray (int [] ary) {for (int i : ary) {system.out.print (i + ""); }}}인쇄
918 562 442 531 210 216 931 706 333 132 첫 번째 지수에 요소의 삽입 위치는 다음과 같습니다. 1 918 562 442 531 210 216 931 706 333 132 두 번째 지수에 요소의 삽입 위치는 다음과 같습니다. 세 번째 지수에 요소의 삽입은 다음과 같습니다. 2 918 562 531 442 210 216 931 706 333 132 네 번째 지수에 요소의 삽입 위치는 다음과 같습니다. 931 706 333 132 여섯 번째 지수에 요소의 삽입 위치는 다음과 같습니다. 0 931 918 562 531 442 216 210 706 333 132 일곱 번째 지수에 요소의 삽입 위치는 다음과 같습니다. 931 918 706 562 531 442 333 216 210 132 9 번째 지수의 요소가 삽입 될 위치는 다음과 같습니다. 9
setValueCount =====> 24
931 918 706 562 531 442 333 216 210 132