binary search Algorithm
The binary search tree algorithm is a fundamental data structure and searching technique used in computer science and programming. It is an efficient and effective way of storing, retrieving, and organizing data in a hierarchical manner. A binary search tree (BST) is a binary tree data structure where each node has at most two child nodes, arranged in a way that the value of the node to the left is less than or equal to the parent node, and the value of the node to the right is greater than or equal to the parent node. This ordering property ensures that a search can be run in logarithmic time, making it a highly efficient method for searching and sorting large datasets.
To search for a specific value in a binary search tree, the algorithm starts at the root node and compares the desired value with the value of the current node. If the desired value is equal to the current node's value, the search is successful. If the desired value is less than the current node's value, the algorithm continues the search on the left subtree. Conversely, if the desired value is greater than the current node's value, the search continues on the right subtree. This process is repeated recursively until either the desired value is found or the subtree being searched is empty, indicating that the value is not in the tree. This efficient search process, which eliminates half of the remaining nodes with each comparison, is the key advantage of using a binary search tree algorithm in data management and search operations.
=begin
Searches through a list for a value in O(log(n)) time.
The list must be sorted.
=end
def binary_search(array, key)
front = 0
back = array.length - 1
while front <= back
middle = (front + back) / 2
return middle if array[middle] == key
key < array[middle] ?
back = middle - 1 : front = middle + 1
end
nil
end
puts "Enter a sorted space-separated list:"
arr = gets.chomp.split(' ').map(&:to_i)
puts "Enter the value to be searched:"
value = gets.chomp.to_i
puts binary_search(arr, value) != nil ?
"Found at index #{binary_search(arr, value)}" :
"Not found"
