Binary Search

What is Binary Search?

Binary search is the fast method of searching for an element in an array. In this approach, we need the array in sorted order.

In Binary search, we first identify the center of the array by dividing the array size by 2. Then, we compare the search element with an element present at the center of the array. If the element at center matches with the search element, we found what we are looking for, so the search is completed successfully.

However, if the center element is not matched with the search element, it is possible that the search element will be either to left of center or right of center as the array is in sorted order.

We check if the search element is smaller to the center element or greater. If the search element is small to center element, we need to search in the left portion of the array. If the search element is greater than the center element, we need to proceed searching in the right portion of the array.

Once we are decided on which portion we need to search, we will again find the center of that portion and match the search element. This process will be repeated until we find the search element. We end the loop when the lower index is of the new portion is not less than the upper index, which means there are no elements left for the search.

The time complexity of binary search is log ₂ n.

Binary Search in Java

package com.techstackjournal;

public class BinarySearch {

	public static void main(String[] args) {

		int[] arr = { 4, 6, 8, 11, 13, 14, 18, 21 };
		int fnum = 21;
		int pos = bindarySearch(arr, fnum);

		if (pos >= 0) {
			System.out.printf("Element found at position %d", pos);
		} else {
			System.out.println("Element not found");
		}

	}

	public static int bindarySearch(int[] arr, int fnum) {

		int lowerIndex, upperIndex, centerIndex;
		lowerIndex = 0;
		upperIndex = arr.length - 1;
		centerIndex = (lowerIndex + upperIndex) / 2;

		while (lowerIndex < upperIndex) {
			if (arr[centerIndex] == fnum) {
				break;
			} else if (arr[centerIndex] > fnum) {
				upperIndex = centerIndex - 1;
			} else if (arr[centerIndex] < fnum) {
				lowerIndex = centerIndex + 1;
			}

			centerIndex = (lowerIndex + upperIndex) / 2;
		}

		if (arr.length > 0 && arr[centerIndex] == fnum) {
			return centerIndex;
		} else {
			return -1;
		}

	}

}

Output:

Element found at position 7

Binary Search in C

#include <stdio.h>

int bindarySearch(int arr[], int length, int fnum)
{

    int lowerIndex, upperIndex, centerIndex;
    lowerIndex = 0;
    upperIndex = length - 1;
    centerIndex = (lowerIndex + upperIndex) / 2;

    while (lowerIndex < upperIndex)
    {
        if (arr[centerIndex] == fnum)
        {
            break;
        }
        else if (arr[centerIndex] > fnum)
        {
            upperIndex = centerIndex - 1;
        }
        else if (arr[centerIndex] < fnum)
        {
            lowerIndex = centerIndex + 1;
        }

        centerIndex = (lowerIndex + upperIndex) / 2;
    }

    if (length > 0 && arr[centerIndex] == fnum)
    {
        return centerIndex;
    }
    else
    {
        return -1;
    }

}

void main()
{

    int arr[] = { 4, 6, 8, 11, 13, 14, 18, 21 };
    int fnum = 21;
    int pos = bindarySearch(arr,8, fnum);

    if (pos >= 0)
    {
        printf("Element found at position %d", pos);
    }
    else
    {
        printf("Element not found");
    }

}

Output:

Element found at position 7

Binary Search in C++

#include <iostream>

using namespace std;

int bindarySearch(int arr[], int length, int fnum)
{

    int lowerIndex, upperIndex, centerIndex;
    lowerIndex = 0;
    upperIndex = length - 1;
    centerIndex = (lowerIndex + upperIndex) / 2;

    while (lowerIndex < upperIndex)
    {
        if (arr[centerIndex] == fnum)
        {
            break;
        }
        else if (arr[centerIndex] > fnum)
        {
            upperIndex = centerIndex - 1;
        }
        else if (arr[centerIndex] < fnum)
        {
            lowerIndex = centerIndex + 1;
        }

        centerIndex = (lowerIndex + upperIndex) / 2;
    }

    if (length > 0 && arr[centerIndex] == fnum)
    {
        return centerIndex;
    }
    else
    {
        return -1;
    }

}

int main()
{

    int arr[] = { 4, 6, 8, 11, 13, 14, 18, 21 };
    int fnum = 21;
    int pos = bindarySearch(arr,8, fnum);

    if (pos >= 0)
    {
        cout<<"Element found at position "<< pos;
    }
    else
    {
        cout<<"Element not found";
    }

    return 0;
}