Binary Search – Best Explanation

Hi Geeks! Today, we going to see about Binary Search Algorithm to search an element in an array.

When an array is sorted, we can apply the binary search algorithm.

There are two ways to search an element in an array.

  1. Linear Search
  2. Binary Search

Linear Search

When an array is unsorted, we can apply the Linear search algorithm.

How Linear Search Works?

It searches the element in an array one by one by comparing with the target element.

Consider the below example, to understand how linear search works.

int[] arr = { 3, 2, 1, 5, 6, 9, 1, 10};
int target = 6;

for(int i=0;i<arr.length;i++)
{
   if(arr[i] == target)
   {
      System.out.println("We have found the given target element in array");
      break;
   }
}

You can notice in the above code, we have searched the element one by one with target element. So, it leads to O(n) run time.

For unsorted array, Linear search is good. No problem with linear search when an array is unsorted.

Problem comes, when an array is sorted. Because when an array is sorted, Binary search performs well, it searches the element with O(logn) run time while Linear search finds the element with O(n) run time.

It pretty much, improved the code.

Binary Search

Binary search is the most popular Search algorithm. It works only with the sorted array.

How Binary Search Works?

Steps to follow

  1. The first step in the binary search algorithm is, find the middle index of the array.

Consider the below example,

int[] arr = { 1, 2, 3, 4, 5, 6, 7};
int searchElement = 5;

Here, we our search element is 5.

Start and end points to the first and last position of indexes
int start = 0; 
int end = arr.length - 1; //6

To find the middle index, sum the start and end, then divide by 2.
int middleIndex = (start + end)/2;
middleIndex = (0 + 6)/2;
middleIndex = 3;

Now the middleIndex is 3.

2. Check arr[middleIndex] is equal to search element.

Here, our search element is 5.
arr[middleIndex] => arr[3] = 4;

It is not equal, since arr[middleIndex] is lower than the search element.

3. If it is not equal, divide the array into two parts of an array.

Part 1 :
start to middleIndex-1

Part 2 :
middleIndex+1 to end

4. Now decide which part array contain the search element.

Part 1 : 
start to middleIndex-1 => 0 to 2

arr[0] = 1;
arr[1] = 2;
arr[2] = 3;


Part 2 :
middleIndex+1 to end => 4 to 6

arr[4] = 5;
arr[5] = 6;
arr[6] = 7;

We can see clearly that, our search element 5 is present in the part 2 array.

if searchElement < arr[middleIndex]
   then the element present in the part 1;
else
   then the element present in the part 2;

In our case, element is present in the part 2.

Logic:

int[] arr = {1, 2, 3, 4, 5, 6, 7};
int searchElement = 5;

while(start <= end)
{
   int middleIndex = (start + end) / 2;
   if(searchElement == arr[middleIndex])
   {
     System.out.println("We found search element at index : "+middleIndex);
     break;
   }
   else if(searchElement < arr[middleIndex])
   {
      //part 1
      end = middleIndex-1;
   }
   else
   {
      //part 2
      start = middleIndex+1;
   }
}

In our case, we have to repeat the process with start from 4th index and end at 6th index.

Iteration second time

start = middleIndex + 1;
so start becomes 4

int middleIndex = (4 + 6) / 2;
middleIndex = 5;

arr[5] = 6;
Our arr[middleIndex] is 6 which is greater than the searchElement. 

So, end becomes middleIndex-1; //part 1 array

end = 5;
Iteration third time, 
Now,
start = 4;
end = 5;

int middleIndex = (4 + 5) / 2;
middleIndex = 4;

arr[middleIndex] => arr[4] = 5;

Now, our searchElement is equal to the arr[middleIndex].
Hence, we found our targeted element at index 5

If you like this article, please subscribe my blog via email.

Join 1,232 other followers

One thought on “Binary Search – Best Explanation

  1. Pingback: Sqrt(x) – Passion of Programming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s