Java is an example of a search and sort using dichotomy
- 2020-05-09 18:36:58
- OfStack
Implement 2 sub - method search
2 division search, the array is required to be an ordered sequence
Two-point search is better than linear search: the more elements an array has, the more efficient it is
The efficiency of two-point search is: O(log2N) N is in the M power range of 2, so the maximum number of times of search is M, log2N means that the M power of 2 is equal to N, omitted constant, O(logN)
If there is an ordered array of 1 200 elements, the maximum number of 2-point searches:
2 to the seventh is equal to 128, 2 to the eighth is equal to 256, and you can see that the seventh power does not reach 200, and the eighth power does, so the maximum number of lookups is equal to 8
// Cycle, 2 searching
static int binarySearch(int[] array, int data) {
int start = 0;
int end = array.length - 1;
int mid = -1;
while (start <= end) {
System.out.println(" Find the number ");
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 2 searching The initial start=0, end = array.length - 1
static int binarySearch4Recursion(int[] array, int data, int start, int end) {
int mid = -1;
System.out.println(" Find the number ");
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;
}
} Two point insertion sort
There is a sequence a[0],a[1]... a [n]; Where a[i-1] is already in order, when a[i] is inserted, the two-point method is used to search for the insertion location of a[i]
Efficiency: O(N^2), for the initial basically ordered sequence, efficiency is not as good as direct insertion sort; For random unordered sequences, the efficiency is higher than that of direct insertion sort
/*
* 2 points ( binary ) Insertion sort
* Equipped with 1 A sequence of a[0],a[1]...a[n]; Among them a[i-1] It was already in order , When inserted into the a[i] when , using 2 Search methods a[i] Insertion position
*/
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, if the order has been sorted, there is no need to move to the right. At this time, the time complexity is: O(n lg n) In the worst case, all inversions, the complexity is zero O(n^2)
* You cannot increase the worst-case complexity to O(n|logn) .
*/
// Print the array
printArray(ary);
}
/**
* Insertion sort
* @param ary
*/
private static void binaryInsert(int[] ary) {
int setValueCount = 0;
// From an array of the first 2 The elements start to sort because no 1 The elements themselves must be sorted
for (int j = 1; j < ary.length; j++) {// The complexity of the n
// Save the current value
int key = ary[j];
// ∆ using 2 Locate the insertion location by searching
// 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(" The first " + j +" The location of the element to be inserted on the index is: " + index);
// Inserts the target into position while moving the element to the right of the target position
for (int i = j; i > index; i--) {// The complexity of the , 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 A number of values (setValueCount)=====> " + setValueCount);
}
/**
* 2 searching ascending recursive
*
* @param ary
* Given a sorted array to look up
* @param target
* To find the target
* @param from
* The starting point of the range you are currently looking for
* @param to
* The return destination of the current lookup
* @return Returns the location of the target in the array, 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, then continue to split
if (range > 0) {
// Select the middle bit
int mid = (to + from) / 2;
// If the critical bit is not satisfied, continue 2 searching
if (ary[mid] > target) {
/*
* mid > target, The ascending rule, target Small, should switch places The front, namely target Located in mid Position,
* According to the Look for ideas, from from to mid-1 That order, so to=mid-1
*/
return binarySearchAsc(ary, target, from, mid - 1);
} else {
/*
* mid < target, The ascending rule, target Larger, do not switch positions, the starting position of the search comparison should be mid+1
*/
return binarySearchAsc(ary, target, mid + 1, to);
}
} else {
if (ary[from] > target) {// Such as 5,4, I'm going to insert 4
return from;
} else {
return from + 1;
}
}
}
/**
* 2 searching In 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) {// Such as 5,4, I'm going to insert 4
return from + 1;
} else {
return from;
}
}
}
/**
* 2 searching In 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) {// Such as 5,4, I'm going to insert 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 first 1 The location of the element to be inserted on the index is: 1
918 562 442 531 210 216 931 706 333 132 The first 2 The location of the element to be inserted on the index is: 2
918 562 442 531 210 216 931 706 333 132 The first 3 The location of the element to be inserted on the index is: 2
918 562 531 442 210 216 931 706 333 132 The first 4 The location of the element to be inserted on the index is: 4
918 562 531 442 210 216 931 706 333 132 The first 5 The location of the element to be inserted on the index is: 4
918 562 531 442 216 210 931 706 333 132 The first 6 The location of the element to be inserted on the index is: 0
931 918 562 531 442 216 210 706 333 132 The first 7 The location of the element to be inserted on the index is: 2
931 918 706 562 531 442 216 210 333 132 The first 8 The location of the element to be inserted on the index is: 6
931 918 706 562 531 442 333 216 210 132 The first 9 The location of the element to be inserted on the index is: 9
set the value times (setValueCount)===== =
>
24
931 918 706 562 531 442 333 216 210 132