How to search a target value in a sorted array using Binary Search. In this tutorial, You are going to learn Binary search algorithm and it’s code implementation 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 at mid, 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) What’s the time complexity of 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
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.
Binary Search in Java
Programming questions for practice
Java program to find the first non-repeated character in a string
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.
