[go: up one dir, main page]
Scribd
Upload
32 views6 pages

Binarry Tree

Binary search is a search algorithm that has O(log n) runtime complexity. It works by dividing the sorted data collection in half at each step, comparing the search key to the middle element and eliminating one half based on the comparison. This process continues recursively on smaller sub-arrays until the key is found or the sub-array is empty. For binary search to work, the data collection must be sorted.

Uploaded by

Thy Ron
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
32 views6 pages

Binarry Tree

Binary search is a search algorithm that has O(log n) runtime complexity. It works by dividing the sorted data collection in half at each step, comparing the search key to the middle element and eliminating one half based on the comparison. This process continues recursively on smaller sub-arrays until the key is found or the sub-array is empty. For binary search to work, the data collection must be sorted.

Uploaded by

Thy Ron
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 6

1- Binary search is a search algorithm with

run-time complexity Ο(log n).


2- This algorithm works on the principle of
divide &conquer.
3- For this algorithm to work properly, the
data collection should be in the sorted
form.
4- Binary search looks for particular item
by comparing middle generality item of the
collection.
If a match occurs, then the index of item is
returned.
If the middle item is greater than the item,
then the item is searched in the sub-array
to the right of the middle item.
Otherwise, the item is searched for in the
subarray to the left of the middle item.
This process continues on the sub-array as
well until the size of the sub-array reduces
to zero.
Binary Search Concept
1- For a binary search to work, it is
mandatory for the target array to be
sorted.
2- First, we shall determine half of the
array by using the following formula:
mid = low + (high - low) /2
Examples of applications
Sort
Tree sort
Binary search trees are used in sorting
algorithms such as tree sort,
where all the elements are inserted at once
and the tree is traversed at an in-order
fashion.
BSTs are also used in quicksort.

Priority queue operations:

Binary search trees are used in


implementing priority queues, using the
node's key as priorities.
Adding new elements to the queue follows
the regular BST insertion operation but the
removal operation depends on the type of
priority queue:
 If it is an ascending order priority queue,
removal of an element with the lowest
priority is done through leftward traversal of
the BST.
. If it is a descending order priority queue, removal
of an element with the highest priority is done
through rightward traversal of the BST.

You might also like