Fold half-finding method :
In an ordered table, compare the data value to be searched with the intermediate element value of the search range, and there will be three situations:
1) If the data value to be found is exactly equal to the intermediate element value, put back the index of the intermediate element value.
2) If the data value to be searched is smaller than the value of the intermediate element, use the first half of the entire search range as the new search range, and execute 1) until an equal value is found.
3) If the data value to be searched is larger than the value of the intermediate element, use the second half of the entire search range as the new search range, and execute 1) until the equal value is found.
4) If the same value cannot be found in the end, an error message will be returned.
According to the binary tree, the middle value is the root of the binary tree, the first half is the left subtree, and the second half is the right subtree. The number of searches for the half-finding search method is exactly the number of layers where the value is located. Under equal probability, approximately
log2(n+1)-1
The code copy is as follows:
//Data is the array to be searched, x is the data value to be searched, beg is the start of the search range, and last is the end of the search range
//Non-recursive method
int BiSearch(int data[], const int x, int beg, int last)
{
int mid;//middle position
if (beg > last)
{
return -1;
}
while(beg <= last)
{
mid = (beg + last) / 2;
if (x == data[mid] )
{
return mid;
}
else if (data[mid] < x)
{
beg = mid + 1;
}
else if (data[mid] > x)
{
last = mid - 1;
}
}
return -1;
}
//Recursive method
int IterBiSearch(int data[], const int x, int beg, int last)
{
int mid = -1;
mid = (beg + last) / 2;
if (x == data[mid])
{
return mid;
}
else if (x < data[mid])
{
return IterBiSearch(data, x, beg, mid - 1);
}
else if (x > data[mid])
{
return IterBiSearch(data, x, mid + 1, last);
}
return -1;
}
//Main function
int _tmain(int argc, _TCHAR* argv[])
{
int data1[60] = {0};
int no2search = 45;
cout << "The array is : " << endl;
int siz = sizeof(data1)/sizeof(int);
for (int i = 0; i < siz; i++)
{
data1[i] = i;
cout << data1[i] << " ";
}
cout << endl;
int index = -1;
//index = BiSearch(data1, no2search, 0, siz);
index = IterBiSearch(data1, no2search, 0, siz);
cout << "Index of " << no2search << " is " << index << endl;
getchar();
return 0;
}
The code copy is as follows:
/**
* Half to find the position of characters in the array (ordered list)
* @param array The retrieved array
* @param x Characters to be found
* @returns The position of the character in the array, no results are found and return -1
*/
function binarySearch(array,x){
var lowPoint=1;
var higPoint=array.length;
var returnValue=-1;
var midPoint;
var found=false;
while ((lowPoint<=higPoint)&&(!found)){
midPoint=Math.ceil((lowPoint+higPoint)/2);
//console.log(lowPoint+"===="+midPoint+"===="+higPoint);
if(x>array[midPoint-1]){
lowPoint=midPoint+1;
}
else if(x<array[midPoint-1]){
higPoint= midPoint-1;
}
else if(x=array[midPoint-1]){
found=true;
}
}
if(found){
returnValue=midPoint;
}
return returnValue;
}
/*var array2=[1,2,3,4,5,6,7,8,9,100,109];*/
var array2=['a','b','c','d','e','f','g'];
console.log(binarySearch(array2,'c'));