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.
function p = binary_search(A,t)
%% Binary Search
% This function binary searches target value (t) in sorted (in increasing order) array A. 
% Binary search compares the target value to the middle element of the
% array. If they are not equal, it determines the half part of array in which the taget might be existed,
% then changes the search range from left or right to half array range and
% repeat searching for this new range. 
% If target can be found in array, this function returns its index.
% If target can not be found in array, it displays "target is not found in
% array"

array_length = length(A);
counter = 0;                                      % number of iteration in searching algorithm
L_SearchRange = 1;                                %initial search range
R_SearchRange = array_length;

while counter <= floor(log(array_length))+1       %maximum iteration needed to find the target
mid = (L_SearchRange + R_SearchRange)/2;

if t == A(floor(mid))
    p = floor(mid);
    break
else if t > A(floor(mid))
        L_SearchRange = floor(mid)+1;
    else 
        R_SearchRange = floor(mid)-1;
        if R_SearchRange == 0            %to stop searching when t is less than the minimum value of array
           counter = counter +1;         
        end
    end 
 counter = counter+1; 
end
end
if counter > floor(log(array_length))+1
    disp('target is not found in aray')
end
end

LANGUAGE:

DARK MODE: