Let’s learn binary search in java.

## Binary search in java

Binary search algorithm is one of the famous fundamental algorithms in computer science. We find application in large number of problems. But here let’s try to understand binary search algorithm.

As you can see above image we have a sorted array of integers.

The size of array is 5. It starts with index 0 to 4. Now given an array we have to find out whether “x” exists in this array or not.

If “x” exists in “numbers” array, then we want to find out the position at which “x” exists in this array. For example, if “x” is 40. Does 40 exist in “numbers”array? Yes 40 exists in the array and it exists at index 3.

Does 70 exists in the above array? No. 70 does not exist in the array. Now what would be the logic to find out whether “x” exists in “numbers” array or not??

Also read – linear search java

One simple approach can be that we can scan the whole array to find the desired number. So we start at index 0 and compare given element with “x”.

If it’s equal to “x”, then we are done with our search. If not, we go to next element.

And we keep on comparing with the next element until we are finished with the array. Let’s say, if we wanted to find 30 in the given array then our search will be over when we reach index 2.

Suppose we want to find 80 in the above array. Our search will be over at index 4 with the conclusion that 80 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 binary search algorithm, we will find “x” at the first position itself. So in the best case we will make only one comparison and we will be able to find the result.

In the worst case when “x” would not even be present in the array, we will scan the whole array and we will make ‘n’ comparisons with all the elements in the array and then we will be able to give back the result that “x” 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 the upper bound of the time taken.

Also read – abstraction in 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 extra property of the array that it is sorted. Let us say we want to find whether number 20 exists in the array “numbers”.

So “x” is 20 and we want to find whether 20 exists in the array “numbers”. We will use different approach this time, instead of comparing “x” with the first element as we did in the case of linear search, we will compare it with the middle element in the array.

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

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

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

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

Initially our search space is the whole array. “x” can exist anywhere in the array. For example let’s say x = 20.

Also read – sort string array java

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

We discard all the elements after 30 and 30 as well. Now the problem gets redefined. We need to search “x” only between index 0 and 1.

So initially the start would be 0 and end would be the last element in the array, in this case the index is 1.

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

middleelement = (start + end) / 2;

Once we find 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 1.

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

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. Now, let’s see java program for binary search,

### Binary search java recursive

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 using iterative approach**

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

**Binary search time complexity:**

T(n) = T(n/2) + c