Write a program to implement Binary Search in Java. In this tutorial, we are going to implement a binary search algorithm in Java. Before implementing this algorithm, let’s first understand what is binary search and how it works.

## Binary Search Algorithm

i) Binary search is a searching algorithm which works with a **sorted array**.

ii) It works by **comparing the middle element of the array** with the search value. If it’s found, its position in the array is returned. If the search value is less than or greater than the middle element, the search continues in the lower or upper half of the array.

iii) The time complexity of the binary search.

a) Best case time complexity of binary search: O(1)

b) Worst case time complexity of binary search: O(logn)

Sorting algorithms and their time complexities

## How Binary Search Works

To understand this let’s take an example. Let’s take an array and value to be searched in an array.

**Example 1**

arr = [11, 15, 16, 19, 25, 36, 67]

search element : 15

**Step 1**: Take two indexes low and high. The value of **low** is 0 and **high** is n-1. After that we have to calculate the value of mid.

low = 0, high = 6

mid = (low + high)/2 = 3, arr[3] is 19, 19 > 15 (19 is greater than 15)

**Step 2**: Searching element < arr[mid], **Search will resume in left half** ( arr[low] to arr[mid-1])

low = 0, high = mid – 1 = 3 -1 = 2, high = 2

mid = (low + high ) / 2 = 1 , arr[1] is 15

So, the value we are searching is found at index 1.

**Example 2**

Let’s take another example.

Programming questions for practice

Java program to find the first non-repeated character in a string

## Program to Implement Binary Search in Java

We have discussed what is binary search and how it works. Let’s implement the binary search algorithm in java. In this programming example, we are going to use an iterative approach.

Recursion vs Iteration – Difference between recursion and iteration

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | import java.util.Scanner; public class BinarySearch { public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.println("Enter the size of an array"); int n = in.nextInt(); // Declare an array int[] arr = new int[n]; System.out.println("Enter the values in a sorted order"); // Input an array values for (int i = 0; i < n; i++) { arr[i] = in.nextInt(); } System.out.println("Enter value to be searched"); int num = in.nextInt(); int low = 0; int high = n - 1; int mid = 0; //Binary Search Logic while (low <= high) { //calculate mid mid = (low + high) / 2; //If arr[mid] is equal to search element if (arr[mid] == num) { System.out.print(" Value found at " + mid); break; } else if (arr[mid] > num) { high = mid - 1; } else if (num > arr[mid]) { low = mid + 1; } } // If value if not found if (low > high) { System.out.println(" Value is not found in an array "); } } } |

I have explained the binary search algorithm and their implementation using java code. In the next tutorial, We will implement binary search algorithm using recursion.