Java dichotomy search _ Power node Java College collation
- 2020-07-21 07:52:04
- OfStack
algorithm
If there is a set of 3, 12, 24, 36, 55, 68, 75, 88 to look up the given value 24. Three variables front, mid and end can be set to point to the upper, middle and lower bounds of the data respectively, mid= (front+end) /2.
Start with front=0 (pointing to 3), end=7 (pointing to 88), and mid=3 (pointing to 36). Because mid > x, so look for it in the first half.
Make the new end= ES20en-1 =2 and front=0 unchanged, then the new mid=1. At this point x > mid, so be sure to look it up in the second half.
Make the new front=mid+1=2, and end=2 unchanged, then the new mid=2, then a[mid]=x, the search is successful. If the number you are looking for is not in the sequence, for example x=25, on the third judgment, x > a[mid], according to the above rule, make front=mid+1, that is, front=3, and front appears > About end,
Indicates that the search was unsuccessful.
Example: Look for the user input data x in an ordered array of N elements. The algorithm is as follows:
1. Determine the search scope front=0, end= ES57en-1, and calculate the middle item mid= (front+end) /2.
2. If a[mid]=x or front > =end, then end the search; Otherwise, continue down.
3. If a [mid]
<
x, indicating that the value of the element to be looked for can only be in a range larger than that of the middle item element, assigns the value of mid+1 to front, recalculates mid, and goes to step 2. If a [mid]
>
x, indicating that the value of the element to be found can only be smaller than the middle element, assigns the value of mid-1 to end, recalculates mid, and goes to step 2.
Algorithm complexity analysis
Time complexity
1. Find the last element (or first element) in the worst case Master theorem T(n)=T(n/2)+O(1) So T(n)=O(logn)
2. In the best case, find the middle element O(1) find the middle element (the middle of the odd-length sequence and the left of the middle of the even-length sequence)
Space complexity:
S (n) = n
package com.bjpowernode.test;
public class BinarySearch {
// Find the number
static int count;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
System.out.println(searchRecursive(array, 0, array.length - 1, 9));
System.out.println(count);
count = 0;
System.out.println(searchLoop(array, 9));
System.out.println(count);
}
/**
* Perform recursion 2 Subsearch, return the 1 The position where the value occurs next
*
* @param array
* Sorted arrays
* @param start
* The starting position
* @param end
* End position
* @param findValue
* The value you want to find
* @return The position of the value in the array from 0 Start. Unable to find return -1
*/
public static int searchRecursive(int[] array, int start, int end,
int findValue) {
// If the array is empty, it returns -1 , that is, the search failed
if (array == null) {
return -1;
}
count++;
if (start <= end) {
// Middle position
int middle = (start + end) / 1;
// The median
int middleValue = array[middle];
if (findValue == middleValue) {
// Is equal to the median value returned directly
return middle;
} else if (findValue < middleValue) {
// If it's less than the median, look before the median
return searchRecursive(array, start, middle - 1, findValue);
} else {
// If it's greater than the median, look after the median
return searchRecursive(array, middle + 1, end, findValue);
}
} else {
// return -1 , that is, the search failed
return -1;
}
}
/**
* cycle 2 Subsearch, return the 1 The position where the value occurs next
*
* @param array
* Sorted arrays
* @param findValue
* The value you want to find
* @return The position of the value in the array from 0 Start. Unable to find return -1
*/
public static int searchLoop(int[] array, int findValue) {
// If the array is empty, it returns -1 , that is, the search failed
if (array == null) {
return -1;
}
// The starting position
int start = 0;
// End position
int end = array.length - 1;
while (start <= end) {
count++;
// Middle position
int middle = (start + end) / 2;
// The median
int middleValue = array[middle];
if (findValue == middleValue) {
// Is equal to the median value returned directly
return middle;
} else if (findValue < middleValue) {
// If it's less than the median, look before the median
end = middle - 1;
} else {
// If it's greater than the median, look after the median
start = middle + 1;
}
}
// return -1 , that is, the search failed
return -1;
}
}