Table of Contents

## Introduction

In this tutorial, we are going to learn about the **Binary Search algorithm** and implement it in **Java**.

Normal **Linear **or **sequential **search algorithm is convenient to use for a small set of data. When the size increases, then in the worst case we require **2 ^{n}** comparisons, where the size of an array or list is

**n**.

Thus we require more efficient algorithms for searching elements. In this tutorial, we are going to explore how binary search is a simple and efficient algorithm as well as how it works.

## The Core Algorithm of Binary Search

For Binary Search, the elements in an array must be in **sorted **order. Let us consider an array that is in ascending order. The Binary search compares elements to be searched, that is, the **key** with the element present in the middle of the data set. It is based on the following three(**3**) basic conditions:

- if the key is
**less**than the middle element, then we now need to search only in the first half of the array, - If the key is
**greater**than the middle element, then we need to only search in the second half of the array, - And if the key is
**equal**to the middle element in the array, then the search ends, - Finally, if the key is
**not found**in the whole array, then it should return a**none**or**-1**. This indicates the element to be searched is not present.

## Example of Binary Search

Consider a sorted array of **10 **integers as given below,

Suppose we are searching for the element **48**. In this case, our key is **48**.

Now, we will have to compare the middle element, which is **25 **with the element that we need to search(**48**). Since `48>25`

, we eliminate the first half and will have to search in the second half for the key.

Further for doing that, we set low as **Mid + 1** and high as the size of the array – 1 or, index of the last element.

In the next iteration, we compare the middle element **55 **with the key. Since `48<55`

, we will have to search the element again in the left half of the array. Correspondingly, the values of low and high are updated as **5**(no change) and** Mid – 1**.

Nextly, now the middle element is **28 **for which we have `48>28`

. Hence, we need to further consider the right portion of the array.

For which now, **low = Mid + 1=6**, and **high = 6 **(no change).

For the next iteration, the middle element is **equal **to the element to be searched, i.e., **48**.

So, we found the number at index **6(Mid)**.

## Implementing Binary Search in Java

Now let us implement the above-mentioned Binary Search Algorithm in java.

public class BinarySearch { public static int binarySearch(int arr[], int low, int high, int key) { int mid = (low + high)/2; while( low <= high ) { if ( arr[mid] < key ) { low = mid + 1; } else if ( arr[mid] == key ) { return mid; }else { high = mid - 1; } mid = (low + high)/2; } if ( low > high ) { return -1; } return -1; } public static void main(String args[]) { int arr[] = {10,18,19,20,25,28,48,55,62,70}; int key = 48; int n=arr.length-1; int index = binarySearch(arr,0,n,key); System.out.println("The sorted array is: "); for(int i=0;i<n;i++) { System.out.print(arr[i] + " "); } System.out.println("\nElement to be searched: "+key); if (index == -1) System.out.println("Unfortunately the Element is not found!"); else System.out.println("The Element is found at the index: "+index); } }

**Output**:

## Complexities of the Binary Search Algorithm

The average number of comparisons for the binary search algorithm is **log _{2}N**. Hence, the

**time complexity**of Binary Search is

**log**.

_{2}nIn terms of **space complexity**, for binary search, it is **O(log n)**. In addition, it takes **O(n)** space to store the array.

Where **n **is the size of the given sorted array.

## Conclusion

So, in this tutorial, we learned about the **Binary Search Algorithm** and its implementation in **Java**. For clear understanding try out the code yourself. For any further questions feel free to use the comments below.

## References

- Binary Search Wikipedia page,
- Binary Search Tree – Journal Dev Article.