You get a bonus - 1 coin for daily activity. Now you have 1 coin

5.6 Binary search (halving method)

Lecture



5.6 Binary search (halving method)



We will assume that we have an array of numbers ordered in ascending order. The main idea is to randomly select some element AM and compare it with the search argument X. If A M = X, then the search is completed; if A M M> X.

The choice of M is completely arbitrary in the sense that the correctness of the algorithm does not depend on it. However, the choice affects its effectiveness. It is clear that our task is to exclude as many elements as possible from the further search. The best solution is to choose the middle element, i.e. middle of the array.

Consider the example shown in Fig. 5.7. Suppose we need to find an element with a key 52. ​​The first element to be compared is 49. Since 49 <52, we are looking for the next middle among the elements located above 49. This number is 86. 86> 52, therefore we are now looking for 52 among the elements located below 86 , but above 49. In the next step, we find that the next value of the middle is equal to 52. We found an element in the array with the specified key.


5.6 Binary search (halving method)


Pseudocode and Pascal programs:

Low = 1

hi = n

while (low <= hi) do

mid = (low + hi) div 2

if key = k (mid) then

search = mid

return

endif

if key
hi = mid - 1

else low = mid + 1

endif

endwhile

search = 0

return

low: = 1;

hi: = n;

while (low <= hi) do

begin

mid: = (low + hi) div 2;

if key = k [mid] then

begin

search: = mid;

exit;

end;

if key
then hi: = mid - 1

else low: = mid + 1;

end;

search: = 0;

exit


If key = 101, the record will be found in three comparisons (in a sequential search, seven comparisons would be needed).

If C is the number of comparisons, and n is the number of elements in the table, then

C = log 2 n.

For example, n = 1024 .

With sequential search C = 512 , and with binary
C = 10 .

You can combine binary and index-sequential search (for large amounts of data), given that the latter is also used when sorted array.

5.7. Search in binary tree



Its purpose is to search for a node of the tree according to a given key. The duration of the operation depends on the structure of the tree. Indeed, a tree can be degenerate into a unidirectional list, like the right one in fig. 5.8.


5.6 Binary search (halving method)


In this case, the search time will be the same as in the unidirectional list, i.e. will have to sort through N / 2 items.

The greatest effect of using the tree is achieved in the case when the tree is balanced. In this case, no more than log 2 N elements should be searched for.

A strictly balanced tree is a tree in which each node has left and right subtrees differing in level by no more than one.

The search for an element in a binary tree is called a binary search in a tree.

Such a tree is called a binary search tree.

The essence of the search is as follows. Analyze the top of the next subtree. If the key is less than the vertex information field, then we analyze the left subtree, more - the right one.

Let the key argument be given

p = tree

whlie p <> nil do

if key = k (p) then

search = p

return

endif

if key
p = left (p)

else

p = right (p)

endif

endwhile

search = nil

return

p: = tree;

whlie p <> nil do

begin

if key = p ^ .k then

begin

search: = p;

exit;

end;

if key


p: = p ^ .left

else

p: = p ^ .right;

end;

search: = nil;

See also


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Structures and data processing algorithms.

Terms: Structures and data processing algorithms.