A popular searching algorithm in Java is the Binary Search algorithm. In this article, I will show you all about its implementation through examples.
1. Introduction
Algorithms like Searching and Sorting are the most popular algorithms in any programming language. They are the basis to understand the fundamentals of programming.
Binary Search in Java is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. It works only on a sorted set of elements. To use binary search on a collection, the collection must first be sorted.
When the binary search is used to perform operations on a sorted set, the number of iterations can always be reduced based on the value that is being searched.
You can also check this tutorial in the following video:
2. Implementing Binary Search Algorithm
Let’s take a look at the below pseudo code to understand it in a better way.
Procedure binary_search A ← sorted array n ← size of array x ← value to be searched Set low = 1 Set high = n while x not found if high < low EXIT: x does not exist. set mid = low + ( high - low ) / 2 if A[mid] x set high = mid - 1 if A[mid] = x EXIT: x found at location mid end while end procedure
Explanation:
Step 1: First, compare x with the middle element.
Step 2: If x matches with the middle element, then you have to return the mid index.
Step 3: Else, If x is greater than the mid element, then x can only lie in the right side half array after the mid element. Hence you recur the right half.
Step 4: Else, if (x is smaller) then recur for the left half.
3. Binary Search examples
Iterative implementation of Binary Search in Java programming language.
// Java implementation of iterative Binary Search
public class BinarySearch {
// Returns index of x if it is present in arr[],
// else return -1
static int binarySearch(int arr[], int x)
{
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
// Driver method to test above
public static void main(String args[])
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = arr.length;
int x = 10;
int result = binarySearch(arr, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at "
+ "index " + result);
}
}
There are two ways to do binary search in Java.
3.1. Arrays.binarysearch() works for arrays which can also be a primitive data type
A sortedArray and an int key, which is to be searched in the array of integers, are passed as arguments to the binarySearch method of the Java Arrays class.
// Java program to demonstrate working of Arrays.
// binarySearch() in a sorted array.
import java.util.Arrays;
public class ArrayBinarySearch {
public static void main(String[] args)
{
int arr[] = { 10, 20, 15, 22, 35 };
Arrays.sort(arr);
int key = 22;
int res = Arrays.binarySearch(arr, key);
if (res >= 0)
System.out.println(key + " found at index = "
+ res);
else
System.out.println(key + " Not found");
key = 40;
res = Arrays.binarySearch(arr, key);
if (res >= 0)
System.out.println(key + " found at index = "
+ res);
else
System.out.println(key + " Not found");
}
}
3.2. Collections.binarysearch() works for object Collections like ArrayList and LinkedList
A sortedList & an Integer key, which is to be searched in the list of Integer objects, are passed as arguments to the binarySearch method of the Java Collections class.
// Java program to demonstrate working of Collections.
// binarySearch()
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class CollectionBinarySearch
{
public static void main(String[] args)
{
List al = new ArrayList();
al.add(1);
al.add(2);
al.add(3);
al.add(10);
al.add(20);
// 10 is present at index 3.
int key = 10;
int res = Collections.binarySearch(al, key);
if (res >= 0)
System.out.println(key + " found at index = "
+ res);
else
System.out.println(key + " Not found");
key = 15;
res = Collections.binarySearch(al, key);
if (res >= 0)
System.out.println(key + " found at index = "
+ res);
else
System.out.println(key + " Not found");
}
}
4. The complexity of the binary search
Complexities like O(1) and O(n) are simple to understand. O(1) means it requires constant time to perform operations like to reach an element in constant time as in case of dictionary and O(n) means, it depends on the value of n to perform operations such as searching an element in an array of n elements.
- Worst-case performance O(log n)
- Best-case performance O(1)
- Average performance O(log n)
5. Linear Search vs Binary Search
A linear search scans one item at a time, without jumping to any item .
- The worst-case complexity is O(n), sometimes known an O(n) search.
- Time taken to search elements keep increasing as the number of elements is increased.
A binary search however, cut down your search to half as soon as you find middle of a sorted list.
- The middle element is looked to check if it is greater than or less than the value to be searched.
- Accordingly, the search is done to either half of the given list.
Differences:
- Input data needs to be sorted in Binary Search and not in Linear Search
- Linear search does the sequential access whereas Binary search access data randomly.
- The time complexity of linear search O(n), Binary search has time complexity O(log n).
- Linear search performs equality comparisons and Binary search performs ordering comparisons
6. Download the Source Code
You can download the full source code of this example here: Binary Search Java Example
