Binary search with and without recursion c++

on
Binary search is a search algorithm that works on sorted arrays or lists by repeatedly dividing the search interval in half. 
Condition : The array must be a sorted array.

binary search algorithm
binary search algorithm



Algorithm for binary search :

  • It begins by comparing the target value to the middle element of the array.

  •  If the target value matches the middle element, the search is successful, and the algorithm returns the index of the middle element. 

  • If the target value is less than the middle element, the search continues in the lower half of the array.

  •  if it is greater, the search continues in the upper half of the array.

  •  The search interval is repeatedly divided in half until the target value is found or until the search interval is empty.

Example of binary search: 

Sure! Here is an example of how binary search works:

Suppose we have a sorted array of integers:

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]



And we want to search for the value 11.


  1. We start by setting two variables, low and high, to the first and last indices of the array respectively:


low = 0
high = 9


  1. We find the middle index of the array by adding low and high and dividing by 2 (integer division):

mid = (low + high) // 2


This gives us mid = 4, so we compare the value at index 4 (9) to our target value 11.


  1. Since 11 is greater than 9, we know that the target value must be in the upper half of the array. We update low to be mid + 1:

low = mid + 1 = 5


  1. We repeat step 2 to find the new middle index of the upper half of the array:

mid = (low + high) // 2 = (5 + 9) // 2 = 7


  1. We compare the value at index 7 (13) to our target value 11.


  1. Since 11 is less than 13, we know that the target value must be in the lower half of the upper half of the array. We update high to be mid - 1:

high = mid - 1 = 6


  1. We repeat step 2 to find the new middle index of the lower half of the upper half of the array:

mid = (low + high) // 2 = (5 + 6) // 2 = 5


  1. We compare the value at index 5 (11) to our target value 11.


  1. Since the two values match, we have found our target value! We return the index 5 where it is located.

This process of repeatedly dividing the search interval in half is the essence of binary search. The time complexity of binary search is O(log n), where n is the size of the array. This makes it very efficient for searching large arrays.


Binary search c++ recursive code : 


int binary_search_recursion(vector<int>&arr , int low , int high , int target)
{
    if(low <= high)
    {
        int mid = low + (high-low)/2 ;
        if(arr[mid] == target)
        {
            return mid;
        }
        else
        if(arr[mid] < target)
        {
            return binary_search_recursion(arr , mid+1  , high , target );
        }
        else
        {
            return binary_search_recursion(arr , low, mid-1 , target);
        }
    }
    return -1;
}



Binary search c++ iterative code : 


int binary_search(vector<int>arr , int low , int high , int target)
{
    while(low <= high)
    {
        int mid = low + (high-low)/2 ;
        if(arr[mid] == target)
        {
            return mid;
        }
        else
        if(arr[mid] < target)
        {
            low = mid+1;
           
        }
        else
        {
            high = mid -1;
        }
    }
    return -1;
}



Time complexity : O(log(n))

Space complexity : O(1)




Comments

Post a Comment