binary search

1. Binary Search
Binary search is also called half search. It is a more efficient search method.
　Binary search requirements: The linear table is an ordered list, that is, the nodes in the table are ordered by keywords, and vectors are used as the storage structure of the table. It may be assumed that the sequence table is in ascending order.

2. The basic idea of ​​binary search
The basic idea of ​​binary search is: (Suppose R[low..high] is the current search interval)
(1) First determine the midpoint position of the interval:
                          (2) Then compare the K value to be checked with R[mid].key: if they are equal, the search is successful and this position is returned. Otherwise, a new search interval must be determined and the binary search continues. The specific method is as follows:
① If R[mid] .key>K, then it can be seen from the orderliness of the table that R[mid..n].keys are all greater than K. Therefore, if there is a node with a key equal to K in the table, the node must be to the left of position mid. In the subtable R[1..mid-1], the new search interval is the left subtable R[1..mid-1].
②Similarly, if R[mid].key Therefore, starting from the initial search interval R[1..n], each time it is compared with the node keyword at the midpoint position of the current search interval, it can be determined whether the search is successful. If it is not successful, the current search The range is reduced by half. This process is repeated until the node with the key K is found, or until the current search interval is empty (that is, the search fails).

3. Binary search algorithm

int BinSearch(SeqList R, KeyType K)
int low=1, high=n, mid; // Set the initial value of the upper and lower bounds of the current search interval
      while (low<=high){ // The current search interval R[low..high] is not empty
                                                                                           Low+High)/2;
If (R [MID] .Key == K) Return mid; // Find successfully returning
if (r [mid] .kdy & gt; k)
hIGH = mid-1; // Continue Search in R[low..mid-1]
                                                                  using with using using using using         out out out through out through   through     through through through through through through off through through off off ‐   ‐ through ‐ through ‐ ‐‐‐‐ ‐ ‐ ‐ ‐ ‐ ‐ ‐ 1 The search interval is empty, and the search failed
      } //BinSeareh
The binary search algorithm is also easy to give its recursive program [see exercises]

4. The execution process of the binary search algorithm
Let the keywords in the input instance of the algorithm be ordered The sequence is
(05, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92)
The keywords K to be found are 21 and 85 respectively. The specific search process [see animation demonstration]

5. Binary search decision tree
The binary search process can be described by a binary tree: the node in the middle of the current search interval is used as the root, and the nodes in the left subtable and right subtable As the left subtree and right subtree of the root respectively. The resulting binary tree is called a decision tree (Decision Tree) or comparison tree (Comparison Tree) that describes binary search.
Note:
The shape of the decision tree is only related to the number of table nodes n, and has nothing to do with the value of R[1..n].keys in the input instance.

【Example】An ordered list with 11 nodes can be represented by the decision tree shown in the figure below.

(1) The composition of the binary search decision tree
　①The circle node is the internal node in the tree. The number inside the circle node in the tree represents the position of the node in the ordered list.
　②External node: All null pointers in the circle node are replaced with a virtual square node, that is, the external node.
　 ③The marks "<", "(", ">", ")" on the left (right) branch connecting a node i in the tree to its left (right) child indicate: when the keyword to be searched K< When R[i].key (K>R[i].key), you should take the left (right) branch to reach the left (right) child of i, and further compare the child's keyword with K. If they are equal, the search process ends and returns, otherwise, K will continue to be compared with the node at the lower level in the tree.

(2) Search of binary search decision tree
Binary search is to compare the given value K with the keyword of the root node of the binary search decision tree. If equal, success. Otherwise, if it is less than the key of the root node, search in the left subtree. If it is greater than the key of the root node, search in the right subtree.
　【Example】For a table with 11 nodes, if the node being searched is the 6th node in the table, only one comparison is needed; if the node being searched is the 3rd or 9th node in the table , two comparisons are required; three comparisons are required to find the 1st, 4th, 7th, and 10th nodes; four comparisons are required to find the 2nd, 5th, 8th, and 11th nodes.
It can be seen that the successful binary search process takes exactly a path from the root of the decision tree to the node being checked, and the number of keywords that have been compared is exactly the number of levels of the node in the tree. If the search fails, the comparison process goes through a path from the root of the decision tree to an external node, and the required number of keyword comparisons is the total number of internal nodes on the path.
【Example】The keyword sequence of the table to be looked up is: (05, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92). To find the record with K=85, the internal The nodes are 6, 9, and 10, and finally the square node "9-10" is reached, and the number of comparisons is 3.
 In fact, the meaning of "i-i+1" in the square node is that the value K to be searched for is between R[i].key and R[i+1].key, that is, R[i].key< ;K

(3) The average search length of binary search
​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​Suppose the total number of internal nodes is n=2h-1, then the tree is determined to be a full binary tree with a depth of h=lg(n+1) (the depth h does not include external nodes) . The number of nodes on the kth level of the tree is 2k-1, and the number of comparisons required to find them is k. Therefore, under the assumption of equal probability, the average search length when a binary search is successful is: ASLbn≈lg(n+1)-1
When a binary search fails, the number of keywords that need to be compared does not exceed the depth of the decision tree. In the worst case, the number of successful comparisons does not exceed the depth of the decision tree. That is: the worst performance and average performance of the two -point search are quite close.

6. Advantages and Disadvantages of Binary Search
Although binary search is efficient, the table must be sorted by keywords. The sorting itself is a very time-consuming operation. Even using an efficient sorting method will take O(nlgn) time.

　Binary search only applies to sequential storage structures. In order to maintain the order of the table, a large number of nodes must be moved during insertion and deletion in the sequential structure. Therefore, binary search is particularly suitable for linear tables that are rarely changed once created and often need to be searched.

For those linear tables that require few searches and often need to be modified, linked lists can be used as storage structures to perform sequential searches. Binary search cannot be implemented on linked lists.

Binary sorting

#include

#include

void TwoInsertSort(int array[],int n)

{
          int left, right, num; j,i;
                                                                                                                while( right >= left)//Binary search for insertion position
                                                                                                                                                                                        use    
Right = middle-1 in the left interval;
Else // The upcoming elements should be in the right interval
left = middle+1;
}
for (j = i-1; j & gt; = left; //Records whose backward sorting code is greater than R[i]
              array[j+1] = array[j];

int rcmp( const int *a, const int *b)
{
return (*a-*b);
}
void main()
{
int array[50];
int i;
printf(" The original array is :n");
for( i=0; i<50; i++ )//The array is initialized and displayed
{
array[i] = 50-i;
printf("array[%d]: %dn", i, array[i]);
}
TwoInsertSort(array,sizeof(array)/sizeof(int));//Binary sorting
printf("nAfter sorted :n");
for( i =0; i<50; i++ )
printf("array[%d]:%dn", i, array[i]);

//Library function bsearch uses binary method to find a specific item in an ordered array number, and returns the address of the number

a = (int *)bsearch(&b, numarray, sizeof(numarray)/sizeof(numarray[0]), sizeof(int),rcmp);

}

For more articles related to dichotomy search, please pay attention to the PHP Chinese website!