Implement dichotomous search
The binary search method requires an ordered sequence in the array. Binary search is more than linear search: the more elements the array is, the more obvious the efficiency is. The efficiency of binary search is expressed: O(log2N) N is in the M power range of 2, so the maximum number of searches is M. log2N means that the M power of 2 is equal to N, omit the constant, and abbreviated as O(logN)
If there is an ordered array of 200 elements, then the maximum number of binary searches:
2^7=128, 2^8=256, it can be seen that the power of 7 cannot reach 200, and the power of 8 includes, so the maximum number of searches is equal to 8
//Loop, binary search static int binarySearch(int[] array, int data) { int start = 0; int end = array.length - 1; int mid = -1; while (start <= end) { System.out.println("Number of searches"); mid = (start + end) >>> 1; if (array[mid] < data) { start = mid + 1; } else if (array[mid] > data) { end = mid - 1; } else { return mid; } System.out.println("start=" + start+",end="+end+",mid="+mid); } return -1; } //Recursive binary search initial start=0, end = array.length - 1 static int binarySearch4Recursion(int[] array, int data, int start, int end) { int mid = -1; System.out.println("Number of searches"); if (start > end) { return mid; } mid = (start + end) >>> 1; if (array[mid] < data) { return binarySearch4Recursion(array, data, mid + 1, end); } else if (array[mid] > data) { return binarySearch4Recursion(array, data, start, mid - 1); } else { return mid; } }Dichotomous insertion sort
There is a sequence a[0], a[1]...a[n]; where a[i-1] is already ordered before it. When inserting a[i], use dichotomy to search for the position of a[i] insertion efficiency: O(N^2). For initial basically ordered sequences, the efficiency is not as good as direct insertion sorting; for random and disordered sequences, the efficiency is higher than the direct insertion sorting.
/* * Bipartite (folded and half) insertion sort* A sequence a[0], a[1]...a[n]; where a[i-1] is already ordered before it. When a[i] is inserted, use dichotomy to search for the position of a[i] insertion*/ public class BinaryInsertSort { public static void main(String[] args) { int len = 10; int[] ary = new int[len]; Random random = new Random(); for (int j = 0; j < len; j++) { ary[j] = random.nextInt(1000); } binaryInsert(ary); /* * Complexity analysis: In the best case, that is, all have been sorted, there is no need to move right. At this time, the time complexity is: O(n lg n) The worst case is, all reverse order, and at this time the complexity is O(n^2) * The complexity of the worst case cannot be improved to O(n|logn). */ // Print the array printArray(ary); } /** * Insert sort* @param ary */ private static void binaryInsert(int[] ary) { int setValueCount = 0; // Sorting from the second element of the array, because the first element itself must be sorted for (int j = 1; j < ary.length; j++) {// Complexity n // Save the current value int key = ary[j]; // ∆ Use binary search to locate the insertion position// int index = binarySearchAsc(ary, ary[j], 0, j - 1);// Complexity: O(logn) // int index = binarySearchDesc(ary, ary[j], 0, j - 1);// Complexity: O(logn) int index = binarySearchDesc2(ary, ary[j], 0, j - 1);// Complexity: O(logn) printArray(ary); System.out.println(""+j +" indexes to be inserted at the position: " + index); // Insert the target into the position, and shift the element to the right of the target position right at the same time for (int i = j; i > index; i--) {// Complexity, worst case: (n-1)+(n-2)+...+n/2=O(n^2) ary[i] = ary[i - 1]; //i-1 <==> index setValueCount++; } ary[index] = key; setValueCount++; } System.out.println("/n Number of values(setValueCount)=====> " + setValueCount); } /** * Binary search ascending recursion* * @param a ary * Given the sorted array to be looked up* @param target * Find the target* @param from * The starting point of the range of the current search* @param to * The return end point of the current search* @return Return the target in the array, where it should be in order*/ private static int binarySearchAsc(int[] ary, int target, int from, int to) { int range = to - from; // If the range is greater than 0, that is, there are more than two elements, continue to split if (range > 0) { // Select the intermediate bit int mid = (to + from) / 2; // If the critical bit is not satisfied, continue to search binary if (ary[mid] > target) { /* * mid > target, ascending rule, target is smaller, and the position should be swapped, that is, target is positioned at the mid position, * According to the search idea, from from to mid-1, it is considered orderly, so to=mid-1 */ return binarySearchAsc(ary, target, from, mid - 1); } else { /* * mid < target, ascending rule, target is large, and no positions are exchanged. The starting position for searching for comparison should be mid+1 */ return binarySearchAsc(ary, target, mid + 1, to); } } else { if (ary[from] > target) {//For example, 5,4, the one to insert is 4 return from; } else { return from + 1; } } } /** * binary search descending order, recursive*/ private static int binarySearchDesc(int[] ary, int target, int from, int to) { int range = to - from; if (range > 0) { int mid = (from + to) >>> 1; if (ary[mid] > target) { return binarySearchDesc(ary, target, mid + 1, to); } else { return binarySearchDesc(ary, target, from, mid - 1); } } else { if (ary[from] > target) {//For example, 5,4, what is to be inserted is 4 return from + 1; } else { return from; } } } /** * binary search descending order, non-recursive*/ private static int binarySearchDesc2(int[] ary, int target, int from, int to) { // while(from < to) { for (; from < to; ) { int mid = (from + to) >>> 1; if (ary[mid] > target) { from = mid + 1; } else { to = mid -1; } } //from <==> to; if (ary[from] > target) {//If 5,4, the one to insert is 4 return from + 1; } 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 The position of insertion of the element on the first index is: 1 918 562 442 531 210 216 931 706 333 132 The position of insertion of the element on the second index is: 2 918 562 442 531 210 216 931 706 333 132 The position of insertion of the element on the third index is: 2 918 562 531 442 210 216 931 706 333 132 The position of insertion of the element on the fourth index is: 4 918 562 531 442 210 216 931 706 333 132 The position of insertion of the element on the fifth index is: 4 918 562 531 442 216 210 931 706 333 132 The position of insertion of the element on the sixth index is: 0 931 918 562 531 442 216 210 706 333 132 The position of insertion of the element on the seventh index is: 2 931 918 706 562 531 442 216 210 333 132 The position of insertion of the element on the eighth index is: 6 931 918 706 562 531 442 333 216 210 132 The location where the element on the 9th index is to be inserted is: 9
SetValueCount =====> 24
931 918 706 562 531 442 333 216 210 132