is an efficient search algorithm that is commonly used for searching a in a . It follows the approach, where the is continuously divided into two halves until the target element is found or the interval becomes empty.
The algorithm begins by finding the of the search interval, which is calculated by averaging the low and high indices. The target element is then compared with the element at the mid-point. If they are equal, the is returned. If the target is smaller, the search continues in the lower half of the interval; otherwise, it continues in the upper half. This process of dividing the interval and comparing the target element with the mid-point is repeated iteratively until the target element is found or the search interval becomes empty.
Binary search offers a of O(log n) where n is the number of elements in the array. This is because with each , the search interval is halved, thus reducing the number of elements to search by half at each step. As a result, binary search significantly outperforms linear search when working with large arrays.
The of binary search is O(1) as it does not require any additional data structures to perform the search. Instead, it only needs a few variables to store indices and perform s.
In addition, binary search is the foundation for the , a common data structure used to store sorted elements. This tree consists of s where each node may have two child nodes. The tree is said to be balanced when the of the left and right subtrees of any node does not differ by more than 1. The nodes of a binary search tree are the ones that do not have any child nodes.
a binary search tree can be done in different orders. In , the left subtree is visited first, then the node itself, and finally the right subtree. starts with the node, followed by the left subtree, and then the right subtree. With , the left and right subtrees are visited before the node. These traversal methods allow efficient access to all the elements in a binary search tree.
Keywords
in-order traversal | index | binary search tree | binary search | pre-order traversal | search interval | traversing | space complexity | mid-point | target element | comparison | time complexity | leaf | post-order traversal | divide and conquer | iteration | sorted array | height | node |
