Q. Write an algorithm and program of binary search.



Binary Search :- Binary search is a fast search algorithm with run-time complexity of search O(log n). For this algorithm to work properly, elements must be in a sorted form.

Binary Search Algorithm

START
   do until the pointers low and high meet each other.
    mid = (low + high)/2
    if (x == arr[mid])
        return mid
    else if (x > A[mid]) // x is on the right side
        low = mid + 1
    else                       // x is on the left side
        high = mid - 1
STOP


Binary Search Program

  • C
  • C++
  • Java
  • Python
  • C#
  • PHP
  • // Binary Search in C
    
    #include <stdio.h>
    
    int binary_search(int array[], int num, int low, int high)
    {
      while (low <= high)
      {
        int mid = low + (high - low) / 2;
    
        if (array[mid] == num)
          return mid;
    
        if (array[mid] < num)
          low = mid + 1;
    
        else
          high = mid - 1;
      }
    
      return -1;
    }
    
    int main(void)
    {
      int array[] = {10, 20, 30, 40, 50, 60, 70, 80};
      int len = sizeof(array) / sizeof(array[0]);
      int num = 40;
      int res = binary_search(array, num, 0, len - 1);
      if (res == -1)
        printf("Element Not found");
      else
        printf("Element is found at index %d", res);
      return 0;
    }
    
    // Binary Search in C++
    
    #include <iostream>
    using namespace std;
    
    int binary_search(int array[], int num, int low, int high)
    {
      while (low <= high)
      {
        int mid = low + (high - low) / 2;
    
        if (array[mid] == num)
          return mid;
    
        if (array[mid] < num)
          low = mid + 1;
    
        else
          high = mid - 1;
      }
    
      return -1;
    }
    
    int main(void)
    {
      int array[] = {10, 20, 30, 40, 50, 60, 70, 80};
      int len = sizeof(array) / sizeof(array[0]);
      int num = 40;
      int res = binary_search(array, num, 0, len - 1);
      if (res == -1)
        cout<<"Element Not found";
      else
        cout<<"Element is found at index "<< res;
      return 0;
    }
    
    // Binary Search in Java
    
    class LFC {
      int binary_search(int array[], int num, int low, int high) {
    
        while (low <= high) {
          int mid = low + (high - low) / 2;
    
          if (array[mid] == num)
            return mid;
    
          if (array[mid] < num)
            low = mid + 1;
    
          else
            high = mid - 1;
        }
    
        return -1;
      }
    
      public static void main(String args[]) {
        LFC ob = new LFC();
        int array[] = { 10, 20, 30, 40, 50, 60, 70, 80 };
        int len = array.length;
        int num = 40;
        int result = ob.binary_search(array, num, 0, len - 1);
        if (result == -1)
          System.out.println("Element Not Found");
        else
          System.out.println("Element is found at index " + result);
      }
    }
    # Binary Search in python
     
    def binary_search (array, num, low, high): 
    
        while low <= high: 
      
            mid = low + (high - low)//2
              
            if array[mid] == num: 
                return mid 
      
            elif array[mid] < num: 
                low = mid + 1
      
            else: 
                high = mid - 1
          
        return -1
    
    array = [ 10, 20, 30, 40, 50, 60, 70, 80 ] 
    num = 40
    
    result = binary_search(array, num, 0, len(array)-1) 
    
    if result != -1: 
        print("Element is found at index " + str(result))
    else: 
        print("Element Not found")
      
    using System;
     
    namespace LFC
    {
        class LFC
        {
            public static void Main()
            {
                int num=40,len=8;
                int []a ={10, 20, 30, 40, 50, 60, 70, 80};
                int low = 0;
                int high = len - 1;
                while (low <= high)
                {
                    int mid = (low + high) / 2;
                    if (num < a[mid])
                        high = mid - 1;
                    else if (num > a[mid])
                        low = mid + 1;
                    else if (num == a[mid])
                    {
                        Console.WriteLine("Element is found at index {0}\n", mid);
                        return;
                    }
                }
                Console.WriteLine("Element Not Found");
            }
        }
    }
    
    function binary_search(Array $arr, $x) 
    { 
        
        if (count($arr) === 0) return false; 
        $low = 0; 
        $high = count($arr) - 1; 
          
        while ($low <= $high) { 
              
           
            $mid = floor(($low + $high) / 2); 
       
          
            if($arr[$mid] == $x) { 
                return $mid; 
            } 
      
            if ($x < $arr[$mid]) { 
              
                $high = $mid -1; 
            } 
            else { 
                
                $low = $mid + 1; 
            } 
        } 
          
       
        return -1; 
    } 
      
    // Driver code 
    $arr = array(10, 20, 30, 40, 50, 60, 70, 80); 
    $value = 40; 
    $val=binary_search($arr, $value);
    if($val>=0) { 
        echo "Element is found at index $val"; 
    } 
    else { 
        echo "Element Not Found"; 
    } 
    
    // Binary Search in C
    
    #include <stdio.h>
    
    int binarySearch(int array[], int num, int low, int high)
    {
      while (low <= high)
      {
        int mid = low + (high - low) / 2;
    
        if (array[mid] == num)
          return mid;
    
        if (array[mid] < num)
          low = mid + 1;
    
        else
          high = mid - 1;
      }
    
      return -1;
    }
    
    int main(void)
    {
      int array[] = {10, 20, 30, 40, 50, 60, 70, 80};
      int len = sizeof(array) / sizeof(array[0]);
      int num = 40;
      int res = binarySearch(array, num, 0, len - 1);
      if (res == -1)
        printf("Element Not Found");
      else
        printf("Element is found at index %d", res);
      return 0;
    }
    

    Output

    Element is found at index 3
    

    Recommended Programs

       Bubble sort program (Descending Order)
       Bubble sort program (Ascending Order)