Binary Search

Binary Search tries to find an element in a sorted array. It compares the middle element of the array with the searched element.
Thus we get 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.     Do 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.     Return -1 if the element that we are looking for i.e N is not found in the array.


Example of Binary Search Binary_Search_Image

Time complexity of Binary Search : Log(N)

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


Python

Python : Binary Search implmentation in Python 3


C++

C++ : Binary Search implementation in C++11


Java : Binary Search implmentation in Java 8

public class Search {

    int BinarySearch( int[] array, int num ) { 
      
        int beg = 0;
        int end = array.length - 1;
        while (beg <= end) {

            int mid = (beg + end) / 2;

            if (array[mid] < num) {
                beg = mid + 1;
            } else if (array[mid] > num) {
                end = mid - 1;
            } else if (array[mid] == num) {
                return mid;
            }
        }
        // Return an index -1 if the number in the sorted array does not exist
        return -1; 
    }   

    public static void main(String[] args) {

        int[] array = { 3, 5, 7, 11, 12, 16, 17, 52, 64, 101 };
        Search s = new Search();

        System.out.println("Number 7 found at index : " + s.BinarySearch (array, 7));
        System.out.println("Number 16 found at index : " + s.BinarySearch (array, 16));
        System.out.println("Number 101 found at index : " + s.BinarySearch (array, 101));
        // Binary Search return an index -1 if the number in the sorted array does not exist
        System.out.println("Number 100 found at index : " + s.BinarySearch (array, 100));
    }   
}

Output of Binary Search implementation in Java.

Number 7 found at index : 2
Number 16 found at index : 5
Number 101 found at index : 9
Number 100 found at index : -1

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