Detailed explanation of javascript half search_javascript skills-JS Tutorial-php.cn

Detailed explanation of javascript half search_javascript skills

WBOY

Release： 2016-05-16 16:17:59

Original

1822 people have browsed it

Half search method:

In an ordered list, when comparing the data value to be searched with the middle element value of the search range, three situations will occur:

1) If the data value to be found is exactly equal to the middle element value, the index of the middle element value will be returned.

2) If the value of the data to be searched is smaller than the middle element value, the first half of the entire search range will be used as the new search range, and 1) will be executed until an equal value is found.

3) If the value of the data to be searched is larger than the middle element value, then the second half of the entire search range will be used as the new search range, and 1) will be executed until an equal value is found

4) If no equal value is found in the end, an error message will be returned.

Understood as a 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 halved search method is exactly the number of levels where the value is located. Under equal probability conditions, it is approximately

log2(n 1)-1

Copy code The code 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;
}

复制代码代码如下:

/**

* Find the position of the character in the array by half (ordered list) 

* @param array The retrieved array

* @param x The character to search for 

* @returns The position of the character in the array, if not found, 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
   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'));