Binary Search Algorithm

2 0
Read Time:5 Minute, 2 Second

Binary Search Algorithm

Binary Search is an efficient algorithm for finding an element in a sorted array by continuously chopping the search area in half.

Why Binary Search?

In Technical Interview you might be given a question like In Given Sorted Array, write a function that returns the index for a given element.

Now, an easy way to solve this problem is with a simple for loop, just loop over every element in the array until you get it.

for(int i = 0;i < arr.Length;i++){
    if(arr[i] == element){
       //found it
}

That going to work but you fail the interview because you need to go faster!

A regular loop results in Linear Time Complexity – O(n)

To go faster you need to use Binary Search which results in Logarithmic Time Complexity – O(log n)

How its Work?

Suppose, I give you a book which has 1000 pages and I said you that open page number 768. So how you will open it? You first open any random page (mostly the middle page), for example, page number 500, now from there book is divided into two parts, now you know that 768 come between 500 -1000 then again you open the random page between 500 and 1000 and you will going to repeat this process until you found the page number 768.

Binary search also works in a similar way.

 Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

Wikipedia

Implementation

C#

using System;

namespace BinarySearch
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nums={2,9,56,66,68,75,123,567};
            int size=nums.Length;
            int element = 123;
            int index=binarySearch(nums,size,element);
            
            Console.WriteLine($"Element {element} has found at {index}");
            
        }
        
        static int binarySearch(int[] arr,int size,int element){
            int low,mid,high;
            low = 0;
            high = size - 1;
            while(low <= high){
                mid = (low+high)/2;
                if(arr[mid] == element ){
                    return mid;
                }
                if(arr[mid]<element){
                    low = mid+1;
                }
                else{
                    high = mid-1;
                }
            }
            return -1;
        }
    }
}

Here in this code, we have the function binarySearch that has 3 parameters – arr(array) , size(array Size),element and returns a integer.

If it finds the element it will return the index of the element but if it didn’t it will return -1.

In that function, it has 3 variables:

  • low – it has the index of the first element
  • mid – it has the index of the middle element
  • high – it has the index of the last element

Then we start the while loop and it will keep running until high becomes smaller or less than low.

Inside this, we calculate the index of the middle element by adding low and high and dividing them by 2, mid = (low+high)/2;

Then we check whether arr[mid] is equal to the element, if it’s, it will return the index and also stops the loop but if it’s not then we will move to the next if condition.

In the next, if condition we check whether the element is greater than the middle element of the array or not. If Yes, then we know that element is somewhere between the middle element and the last element, so we need to search for it in between the middle and last, so we will change the low and set it equal to the index of that element that is on the right side of the middle (mid +1). But if No, then we know that element is somewhere between the middle element and the first element, so we need to search for it in between the first and middle, so, we will change the high and set it equal to the index of the element that is left side of a middle element (mid – 1).

And we are now in a loop so it will go back to the starting point where we calculate mid, as we have a new low or high, so it’s necessary to recalculate the mid. After getting a new mid we again check whether arr[mid] equal to the element, If yes, we find it, if no, we will move to the next if condition where we again check whether the element is greater than the middle element of the array and according to it we will again set new low and high until we find it.

Same Code but Different Language!

Python

#Binary Search Example in Python

def binarySearch(arr, size, element):
    low = 0
    high = size - 1
    while low <= high:
        mid = (low + high)//2
        
        if arr[mid] == element:
            return mid
        if arr[mid] < element:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1


nums = [2,9,56,66,68,75,123,567]
size=len(nums)
element = 123
index=binarySearch(nums,size,element)

print("Element ", element, "has found at ", index)

#Binary Search Example in Python

Java

public class BinarySearch
{
    public static void main(String[] args) {

	int[] nums={2,9,56,66,68,75,123,567};
        int size=nums.length;
        int element = 123;
        int index=binarySearch(nums,size,element);
        
        System.out.printf("Element %d has found at %d",element,index);
	}


    static int binarySearch(int[] arr,int size,int element){
            int low,mid,high;
            low = 0;
            high = size - 1;
            while(low <= high){
                mid = (low+high)/2;
                if(arr[mid] == element ){
                    return mid;
                }
                if(arr[mid]<element){
                    low = mid+1;
                }
                else{
                    high = mid-1;
                }
            }
            return -1;
        }
}

Conclusion

Binary Search is one of the efficient algorithm to find elements in a sorted array, especially for those arrays which are huge in size. But sometimes Binary search is not the best way to find elements in the array which are shorter in length/size, for short array linear search is ok.

Happy
Happy
67 %
Sad
Sad
0 %
Excited
Excited
0 %
Sleepy
Sleepy
0 %
Angry
Angry
0 %
Surprise
Surprise
33 %

Average Rating

5 Star
0%
4 Star
0%
3 Star
0%
2 Star
0%
1 Star
0%

Leave a Comment