Binary Search

Binary Search tries to find if an element is present in a sorted array. It compares the middle element of the array with the element being searched.
Thus we have the following cases,

Case 1 : If the middle element equals the searched element, the position of the middle element is returned.
Case 2 : If the middle element is bigger than the searched element, the left part of the array is searched using the same logic i.e binary search.
              Left part of the array : [ 0 … mid - 1 ]
Case 3 : If the middle element is smaller than the searched element, the right part of the array is searched using the same logic i.e binary search.
              Right part of the array : [ mid + 1 … end - 1 ]


Algorithm : Binary Search

1. Binary Search ( Array, Search element N )
2.     Beg = 0, End = Sizeof ( Array ) - 1
3.     While ( Beg <= End )
4.         Mid = Beg + ( End - Beg ) / 2
5.         If ( Array [ Mid ] == N )
6.             Return Mid as the index of the found element N.
7.         Else If ( Array [ Mid ] < N )
8.             Beg = Mid + 1.
9.         Else
10.            End = Mid - 1.
11.     If the element that we are looking for i.e N is not found in the array, Return -1


Example Binary_Search_Image

Time complexity : Log ( N )


Why is mid calculated as mid = beg + (end-beg)/2 ?

Integer range is -2,147,483,648 to 2,147,483,647. If you are searching in an array of size 2,000,000,000 and the element searched for is located at index 1,999,999,999. When you search in the upper half of array, beg=1,000,000,001 and end=2,000,000,000. If mid is calculated as (low+high)/2, low+high = 3,000,000,001; which exceeds the range of int, resulting in overflow errors. But mid calculated as beg + (end-beg) = 1,000,000,001 + 999,999,999 = 2,000,000,000; which fits in the integer range.



Binary Search Implementation

from typing import List # For annotations

def BinarySearch (array : List[int], n : int) :

    beg = 0
    end = len(array) - 1 

    while (beg <= end) :

        mid = int(beg + (end-beg)/2)

        if (array[mid] == n) :
            return mid 
        elif (array[mid] < n) :
            beg = mid + 1;  
        else :
            end = mid - 1

    return -1; 

array = [ 3, 5, 7, 11, 12, 16, 17, 52, 64, 101 ]

print("Array : " + str(array))
n = int(input("Element to search : "))
index = BinarySearch (array, n)

if (index != -1) :
    print("Element found at index : " + str(index))
else :
    print("Element not found. ")

Output

Array : [3, 5, 7, 11, 12, 16, 17, 52, 64, 101]
Element to search : 17
Element found at index : 6

Array : [3, 5, 7, 11, 12, 16, 17, 52, 64, 101]
Element to search : 52
Element found at index : 7

Array : [3, 5, 7, 11, 12, 16, 17, 52, 64, 101]
Element to search : 64
Element found at index : 8

Array : [3, 5, 7, 11, 12, 16, 17, 52, 64, 101]
Element to search : 3
Element found at index : 0

Array : [3, 5, 7, 11, 12, 16, 17, 52, 64, 101]
Element to search : 4
Element not found. 
#include<iostream>
#include<vector>

int BinarySearch (std :: vector<int> &vec, int n) { 

    int beg = 0;
    int end = vec.size() - 1;

    while (beg <= end) {

        /* Avoid calculating mid as (beg+end)/2. As (beg+end)
           might exceed the range of an integer causing overflow
           resulting in errors */

        int mid = beg + ( end - beg ) / 2;

        if (vec[mid] == n)
            return mid;
        else if (vec[mid] < n)
            beg = mid + 1;  
        else
            end = mid - 1;
    }   

    return -1; 
}

int main() {

    int n, index;
    std :: vector<int> vec = { 3, 5, 7, 11, 12, 16, 17, 52, 64, 101 };

    std :: cout << "Array elements :";
    for (auto& i : vec) {
        std :: cout << i << " ";    
    } std :: cout << std :: endl; 

    std :: cout << "Element to search : ";
    std :: cin >> n;   
        
    if((index = BinarySearch (vec, n)) != -1) 
        std :: cout << "Element found at index : " <<  index << std :: endl;
    else
        std :: cout << "Element not found. " << std :: endl;
    return 0;
}

Output

Array elements :3 5 7 11 12 16 17 52 64 101 
Element to search : 11
Element found at index : 3

Array elements :3 5 7 11 12 16 17 52 64 101 
Element to search : 7
Element found at index : 2

Array elements :3 5 7 11 12 16 17 52 64 101 
Element to search : 64
Element found at index : 8

Array elements :3 5 7 11 12 16 17 52 64 101 
Element to search : 100
Element not found. 
import java.util.Scanner;

class Search {

    int BinarySearch (int array[], int element) {

        int beg = 0;
        int end = array.length - 1;

        while (beg <= end) {

            // Find the index of the middle element
            int mid = beg + (end - beg) / 2;

            // If the element to be searched is the middle element, return its position
            if (array[mid] == element) {
                return mid;
            } else if (array[mid] < element) {
            // If the element is less than the middle element, search the left side of the middle element
                beg = mid + 1;
            } else {
            // If the element is greater than the middle element, search only the right side of middle element
                end = mid - 1;
            }
        }
        return -1;
    }

    public static void main (String args[]) {

        Search s = new Search();

        int[] array = { 2, 4, 15, 16, 70, 81, 99 };
        for (int i=0; i<array.length; i++)
            System.out.print(array[i] + " ");
        System.out.println();

        // Get the input from the user for the element to be searched
        Scanner input = new Scanner(System.in);

        System.out.print("Enter the element to be searched: ");

        int element = input.nextInt();
        input.close();

        int index;
        if ((index = s.BinarySearch (array, element)) != -1) {
            System.out.println("Element found at index: " + index);
        } else {
            System.out.println("Element not found.");
        }
    }
}

Output

$ java Search 
2 4 15 16 70 81 99 
Enter the element to be searched: 81
Element found at index: 5

2 4 15 16 70 81 99 
Enter the element to be searched: 2
Element found at index: 0

2 4 15 16 70 81 99 
Enter the element to be searched: 99
Element found at index: 6

2 4 15 16 70 81 99 
Enter the element to be searched: 100
Element not found.



Copyright (c) 2019-2024, Algotree.org.
All rights reserved.