Binary Search Program In Java

Sharing is healthy !!

Today, we will delve into binary search program in java which uses Scanner class in java.util package.

what is binary search?

Binary search is one of the famous fundamental algorithms in computer science.

We find application of binary search in large number of problems. But here let’s try to understand in it’s simplest form.

Binary Search Program In Java

As you can see in the image above we have a sorted array of integers. Let’s say the name of this array is “numbers”.

int[] numbers = {10, 20, 30, 40, 50};

The size of the array is five. So we have index starting at zero till four.

Now given an array and a number or an integer “y”, we have to find out whether “y” exists in this array or not.

And if “y” exists in this array, then we want to find out the position at which “y” exists in this array.

So for example if “y” is forty. Does forty exist in the array? Yes forty exists in the array “numbers” and it exists at index three.

Does seventy exists in the array? No seventy does not exist in the array.

Now what would be the logic to find out whether “y” exists in this array or not??

One simplest approach can be that we can scan the whole array to find out the desired number.

So we start at index zero and compare given element with “y”.

If it’s equal to “y”, then we are done with our search, we have found the element in the array. If not we go to the next element.

And we keep on comparing with the next element until we are finished with the array or we find the number.

Let’s say if we wanted to find thirty in the given array then our search will be over when we reach index two.

If we wanted to find eighty our search will be over at index four with the conclusion that eighty does not exist in the array.

This approach will work irrespective of whether the array is sorted or not and if I have to write code for this it will be pretty straight forward.

Now, with this algorithm, if we are lucky we will find “y” at the first position itself.

So in the best case we will make only one comparison and we will be able to find result.

In the worst case when “y” would not even be present in the array, we will scan the whole array, we will make ‘n’ comparisons with all the elements in the array and then we will be able to give back the result that “y” does not exist in the array.

It’s always good to analyze the running time of an algorithm in the worst case and find out the upper bound of the time taken.

Now in this case the time taken grows as a linear function of “n”. So we also call this as linear search.

If we are using linear search, we are not using any property like the array sorted or not, this will work.

Now let us try to improve this algorithm using the extra property of the array that it is sorted.

Let us say we want to find out whether number twenty exists in the array “numbers”.

So “y” is twenty and we want to find out whether “y” exists in the array “numbers”.

We will use different approach this time, instead of comparing “y” with the first element as we do in the case of linear search, we will compare it with the middle element in the array.

Now the size of this array is five, so the middle element will be at index two.

Binary Search Program In Java

Here there can be three cases

Case one : y == numbers[middle_element]
Case two : y < numbers[middle_element]
Case three : y > numbers[middle_element]

Clearly, if “y” is equal to the middle element, our search is over. Because we have found “y” in the array.

If “y” is less than the middle element then because the array is sorted it lies before the middle element and we can discard middle element and all the elements after middle element.

Similarly if “y” is greater than the middle element it lies after the middle element so we can discard all the elements before the middle element.

And of course the middle element as well. So in case two and three we discard half the elements from our search space and reduce our search space.

In this example when “y” is twenty, initially our search space is the whole array. “y” can exist anywhere in the array.

Now we compare it with the middle element which is thirty. Now “y” is less than thirty, so it should exist somewhere before thirty.

So we discard all the elements after thirty and thirty as well. So now the problem gets redefined.

We need to search “y” only between index zero and one.

So how do we keep track of the search space? We keep track of the search space using two indices start and end.

So initially the start would be zero and end would be the last element in the array, in this case the index four.

Because initially the whole array is our search space and we calculate middle element as

middle_element = (start + end) / 2;

Once we find out our reduced search space, we adjust start and end accordingly.

In this case, after comparing twenty with thirty and discarding half of the array, our end now becomes index one.

Now we again find out the middle element in this reduced space.

So here the middle element will be one plus zero by two, if we take only the integral part, one plus zero by two would be zero point 5 (0.5).

If we take the integral part the middle element will be index zero. Once again is it equal to “y”? No, ten is not equal to twenty.

Is “y” less than the middle element, is is it case two? No it is not.

“y” is greater than the middle element, this time we discard the middle element and all the elements towards its left.

So “y” is now equal to middle element. We have found our element. So we are done with our search.

This kind of search where we reduce the search space into half at each comparison is called binary search.

We are able to reduce the search space into half only because the array is sorted.

Array being sorted is a precondition for binary search.

Ok, let’s see an example for binary search in java,

Example: Binary Search Program In Java

Also Read – Calculate Average of an Array in Java

import java.util.Scanner;

public class BinarySearch 
{
public static void main(String[] args) 
{
int x;
int first, last, middle;
int y;
int search;
int[] array;

Scanner sc = new Scanner(System.in);
System.out.println("Please enter number of elements: ");
y = sc.nextInt();
array = new int[y];

System.out.println("Please enter " + y + " numbers: ");

for(x = 0; x < y; x++)
array[x] = sc.nextInt();

System.out.println("Please enter value to search: ");
search = sc.nextInt();

first = 0;
last = y - 1;
middle = (first + last) / 2;

while(first <= last)
{
if(array[middle] < search)
first = middle + 1;
else if(array[middle] == search)
{
System.out.println("The number " + search + " is at location " + (middle + 1) + ".");
break;
}
else
last = middle - 1;
middle = (first + last) / 2;
}
if(first > last)
System.out.println("The number " + search + " is not present in the list.");
sc.close();
}
}

Output:

Binary Search Program In Java


using arrays class

import java.util.Arrays;

public class BinarySearchDemo
{
public static void main(String[] args)
{
char name[] = { 'f', 'l', 'o', 'w', 'e', 'r' }; 

System.out.println("The letter 'o' is at index : " + Arrays.binarySearch(name, 'o') + ".");
System.out.println("The letter 'r' is at index : " + Arrays.binarySearch(name, 'r') + ".");
}
}

Output:

The letter ‘o’ is at index : 2.
The letter ‘r’ is at index : 5.


Using method

public class BinaryExample
{
public static void main(String[] args)
{
BinaryExample be = new BinaryExample();
int[] arr = {10, 20, 30, 40, 50};       
System.out.println("The index position is : " + be.mySearch(arr, 30));
int[] arr1 = {110, 120, 130, 140, 150};        System.out.println("The index position is : " + be.mySearch(arr1, 150));
}

public int mySearch(int[] input, int key)
{
   int start = 0;
   int end = input.length - 1;
   while (start <= end)
   {
      int middle = (start + end) / 2;
      if (key == input[middle])            
      {
         return middle;           
      }
      if (key < input[middle])
      {
         end = middle - 1;
      }
      else
      {
         start = middle + 1;
      }
   }
   return -1;
 }
}

Output:

The index position is : 2
The index position is : 4


conclusion

That’s it guys. This is all about binary search program in java with detailed explanation on the concept.

I hope you have enjoyed the post and understood the concept.

You can subscribe to my blog flower brackets if haven’t already.

Do share this post if you like.

Sharing is healthy !!

Leave a Reply

Your email address will not be published.