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.

[jetpack_subscription_form show_only_email_and_button=”true” custom_background_button_color=”undefined” custom_text_button_color=”undefined” submit_button_text=”Subscribe” submit_button_classes=”undefined” show_subscribers_total=”true” ]

0 thoughts on “Binary Search – Best Explanation”

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

Leave a Comment

Your email address will not be published. Required fields are marked *