Binary Search in Java

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

 

Binary Search Algorithm

Binary Search Algorithm

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)

Subscribe Our Tutorials

Get Latest Updates on Facebook

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.

Binary Search in Java

Binary Search in Java

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

 

 

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.

About WebRewrite

I am technology lover who loves to keep updated with latest technology. My interest field is Web Development.
Tagged , , . Bookmark the permalink.