BINARY SEARCH ALGORITHM

WHAT THIS ALGORITHM IS ALL ABOUT?

N.B -  This post requires a basic understanding of functions and recursion

Before you decide to jump into this algorithm, I would like you to skim through the LINEAR SEARCH algorithm for a better understanding of what searching algorithms are and their mechanism as well as the working principle.

So as the name suggests "Binary" means two. So precisely we are interested more upon dividing the given array into two parts and searching the key value.

Well, that's the main concept but that's not how a good programmer should code.

I mean to say, when we have operations like "recursion" and "sorting" with us, then let's have a better approach of accomplishing the task of searching.

Suppose you are given an array as below,

Lets's sort the array and we will get something as follows,

Suppose the key value is = 6 means we have to search for the index of the array where 6 is present.

Let us follow the recursive algorithm (Look at the code for better understanding)

1. Find the middle index of the array
2. Check if the middle index has the value same as that of key
1. if yes, return mid
2. if no
1. call the function again by dividing the array to left half means from index 0 to mid-1.
2. call the function again by dividing the array to right half means from index mid+1 to size-1, where size is the total array size.

Have a look at the code below,

C++ Code:

#include<bits/stdc++.h>

using namespace std;

void Binary_search_helper(int* input,int starting_index,int ending_index,int key)

{

    if(starting_index <= ending_index)

    {

    int mid = (ending_index + starting_index)/2;

    if(key == input[mid])

    {

        cout << "The key value is present at "<< mid << " index of the sorted array " << endl;

    }

    else if(key < input[mid])

    {

        Binary_search_helper(input,starting_index,mid-1,key);

    }

    else

    {

        Binary_search_helper(input,mid+1,ending_index,key);

    }

    }

    else

    {

        cout << "Not present in the array" << endl;

    }

}

void Binary_search(int* input,int size, int key)

{

    Binary_search_helper(input,0,size-1,key);

}

int main()

{

    int n,key;

    cout << "Please enter the size of the array : " ;

    cin >> n;

    int a[n];

    cout << "Please enter the array : ";

    for(int i=0;i<n;i++)

    {

        cin >> a[i];

    }

    cout << "Please enter the key value to search : ";

    cin >> key;

    sort(a,a+n);

    Binary_search(a,n,key);

    return 0;

}

Python Code:

def Binary_search(arr,starting_index,ending_index,key):

    if (ending_index >= starting_index):

        mid = int((starting_index+ending_index)/2)

        if(arr[mid] == key):

            print("key is present at index {} of the sorted array".format(mid))

        elif(arr[mid]>key):

            Binary_search(arr,starting_index,mid-1,key)

        elif(arr[mid]<key):

             Binary_search(arr,mid+1,ending_index,key)

    else:

        print("Key value is not present in the array")

arr=list(map(int,input("Please Enter the array : ").split()))

key = int(input("Please enter the key value to search : "))

arr.sort()

Binary_search(arr,0,len(arr),key)

In the C++ code Binary_search_helper() is the function that is called recursively to search for the key value and in recursion Binary_search() is the similar function.

Very soon we will post three programming problems on this algorithm and discuss how variation in algorithm occurs with its time complexity and memory allotment.

Hope that helps. Keep Coding :)