Hey guys!! Welcome to flower brackets blog. Today, we will delve into binary search java.

#### How do you do binary search?

Binary search algorithm 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 its simplest form.

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 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” that 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??

Also read – linear search java

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 binary search 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 binary search complexity or running time of an algorithm in the worst case and find out the upper bound of the time taken.

Also read – sparse matrix java

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 binary search 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 20 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.

Here there can be three cases

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

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 of 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.

Also read – sort string array java

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

So we discard all the elements after 30 and 30 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 is four.

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

middleelement = (start + end) / 2;

Once we find out our reduced search space, we adjust start and end accordingly. In this case, after comparing 20 with 30 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, it will be index zero. Once again is it equal to “y”? No, 10 is not equal to 20. Is “y” less than the middle element, 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 algorithm. Ok, let’s see recursive implementation of binary search in java,

#### Example : binary search java

public class BinarySearchExample { int Search(int arrNum[], int left, int right, int m) { if(right >= left) { int mid = left + (right - left) / 2; // checking if element is present in middle if(arrNum[mid] == m) return mid; // checking if element is small than middle element if(arrNum[mid] > m) return Search(arrNum, left, mid - 1, m); // if not element can only be present in right return Search(arrNum, mid + 1, right, m); } // we come out of the loop if not present in array return -1; } public static void main(String[] args) { BinarySearchExample bse = new BinarySearchExample(); int arrBinary[] = {1,4,6,14,32}; int num = arrBinary.length; int a = 14; int result = bse.Search(arrBinary, 0, num - 1, a); if(result == -1) { System.out.println("Sorry!!Element is not present"); } else { System.out.println("Element found at index : " + result); } } }

**Output :**

Element found at index : 3

**Binary search java – iterative approach**

Now let’s java program to perform binary search iteratively. Here’s the code,

public class BinaryIterativeDemo { // here code returns index of variable y in the array else return -1 int searchBinary(int arrNum[], int y) { int left = 0, right = arrNum.length - 1; while(left <= right) { int m = left + (right - left) / 2; // checking if variable y is present at middle if(arrNum[m] == y) return m; // check if variable y is greater, neglect left if(arrNum[m] < y) left = m + 1; // check if variable y is smaller, neglect right else right = m - 1; } // we come out of the loop if not present in array return -1; } public static void main(String[] args) { BinaryIterativeDemo bs = new BinaryIterativeDemo(); int arrBinary[] = {1, 4, 6, 14, 32}; int x = 32; int output = bs.searchBinary(arrBinary, x); if(output == -1) { System.out.println("Sorry!!Element not present"); } else { System.out.println("Element found at index : " + output); } } }

**Output:**

Element found at index : 4