In this quick tutorial, we’ll learn to** perform a binary search in a sorted array.** We’ll also write our own algorithmic implementation in Java. Later, we’ll discuss the *binarySearch()* method available in the Java library.

Let’s say we have a sorted array *a[]*:

1 |
int[] a = {1, 2, 3, 4, 5, 6}; |

And we want to search for a given element *x* in *a[]*. One approach of searching is to traverse through all the elements in our array and look for *x *in it. However, this approach doesn’t take an advantage of the fact that we have a sorted array.

We as developers always ask: ‘Can we do better?’

The answer here is yes. We’ll use the binary search algorithm to do so.

**Binary search is a decrease-and-conquer algorithm** i.e. it reduces the problem domain to half in each iteration till we have it solved. The algorithm has the following steps:

- Set
*low = 0, high = n-1* - Finding the middle element in the array
- If the
*middle element == x*then return the current index, Or - If the
*x > middle element*, then set*low = mid + 1*(As it means*x*exists in the right half) - If
*x < middle element*, set*high = mid – 1*(As it means*x*exists in the left half) - Repeat starting from step 2 till
*low <= high*holds*true*

Let’s implement it in Java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
int binarySearch(int[] a, int n, int x) { int low = 0, high = n-1; while(low <= high) { int mid = low + (high-low)/2; if(a[mid] == x) return mid; else if(x > a[mid]) low = mid + 1; else high = mid - 1; } //element x not found return -1; } |

**Clearly, in each** **iteration, we’re making a decision to search either in the left half or the right half of the remaining search space till we find the element**. In case we still can’t find it, it simply means no such element exists. In that case, we’re returning* -1*.

**Please note that we’ll have an unpredictable output if the array is unsorted.**

Implementing binary search algorithm recursively is also pretty straightforward. So, our recursive algorithm implementation in Java would look like:

1 2 3 4 5 6 7 8 9 10 11 12 13 |
int binarySearch(int a[], int low, int high, int x) { if(low > high) return -1; int mid = low + (high - low)/2; if(a[mid] == x) return mid; else if(x < a[mid]) return binarySearch(a, low, mid - 1, x); else return binarySearch(a, mid + 1, high, x); } |

Our recursive implementation accepts *low* and *high* as well as the part of its method arguments. To search for *x=5*, we’ll invoke this method as:

1 |
int index = binarySearch(a, 0, a.length - 1, 5); |

Having looked at how to implement a binary search algorithm, let’s discuss the helper method available in our* java.util.Arrays* class in Java:

1 2 |
//x being the element we're looking for int index = Arrays.binarySearch(a, x); |

This method returns the index of the searched element if it exists in the sorted array. **In case no such element exists, this method returns -(insertion point + 1) as an output. The insertion point is the index at which the key would exist in the array if it would have been present.**

So, for example:

1 2 3 4 |
int[] a = {1, 2, 3, 4, 6, 7}; int indexOf4 = Arrays.binarySearch(a, 4); // indexOf4 = 3 int indexOf5 = Arrays.binarySearch(a, 5); // indexOf5 = -5 |

Similar to *Arrays.binarySearch()*, we also have a method *binarySearch()* in our *Collections* class in Java. It helps us perform a binary search on some form of a *Collection* like an *ArrayList* or a *LinkedList:*

1 2 3 4 5 6 |
List<Integer> list = new ArrayList(); list.add(1); list.add(2); list.add(4); int indexOf2 = Collections.binarySearch(list, 2); // indexOf2 = 1 |

In this tutorial, we looked at the iterative as well as the recursive solution to implement the binary search algorithm in Java. We also discussed the* Arrays.binarySearch()* and *Collections.binarySearch()* utilities available in our Java library.

Be the First to comment.