What does Searching mean
Searching means to check if an element exists in a collection and finding the location of that element, if it exists. Searching is usually performed on arrays.
There are 3 types of search available:
A. Linear search,
B. Binary Search and
C. Interpolation Search.
This post will focus on Binary Search.
What is Binary Search
Binary search looks for an element by dividing the array into half. Its operation is based on the following algorithm:
- Compare the element to be searched with the middle element of array.
- When the middle element and element to search are equal, then return index of middle element.
- If the middle element is greater than the element to search, then search for element in the left half of array.
- When the middle element is less than the element to search, then search for element in the right half of array.
- Continue dividing the array till the element is found or complete array has been searched.
Binary Search requires that the array is sorted in ascending order of elements.
This makes sense because if the array is sorted and middle element is greater than the element to search, the element will be in the left half else it will be in right half.
Binary search is faster as compared to Linear search as the searching is performed by dividing the array into half which means there are lesser comparisons.
Time complexity for this algorithm is O(log n).
Binary Search in Java
Binary search can be performed using a java program which follows the algorithm written above.
There are multiple ways a binary search can be performed in java.
Method 1: Using iterative approach
This approach iterates over the array. In every iteration, it compares the element at middle position of array with the element to search.
If both are equal, it returns the middle element index or prints a success message(depends on your implementation).
If the middle element is less than the searched element, this means that element might be in left half of array, thus the position of end of array is reset to the position of one element prior to middle element.
If the middle element is greater than the searched element, this means that element might be in right half of array, thus the position of start of array is reset to the position of one element after middle element.
Array should be sorted in ascending order of elements for this approach to work successfully.
public class BinarySearch {
public int binarySearchIterative(int[] array, int element) {
// start position of array
int startIndex = 0;
// end position of array
int endIndex = array.length;
// loop till whole array is covered
while (startIndex < endIndex) {
// calculate middle array position
int middleIndex = (startIndex + endIndex) / 2;
if (array[middleIndex] == element) {
// element found at middle position
return middleIndex;
} else if (array[middleIndex] < element) {
// move the start index past middle index so that right portion
// of array is searched
startIndex = middleIndex + 1;
} else {
// move the end index before middle index so that left portion
// of array is searched
endIndex = middleIndex - 1;
}
}
System.out.println("Element not found in array");
return -1;
}
public static void main(String[] args) {
// initialize array
int arr[] = { 5, 10, 15, 20, 25, 30 };
// element to search
int element = 30;
int index = new BinarySearch().binarySearchIterative(arr, element);
if (index != -1) {
System.out.println("Element found at index " + index);
}
}
}
Output
Element found at index 5
Method 2: Using recursive approach
Implementation of above mentioned algorithm to find an element using binary search can also be done using recursive method.
This approach requires a helper method which accepts the array, start and end indexes of array in which the searching will be performed and the element to be searched as arguments.
Array should be sorted in ascending order of elements for this approach to work successfully.
public class BinarySearch {
public int binarySearchRecursive(int[] array, int element) {
return binarySearchRecursive(array, 0, array.length - 1, element);
}
/**
* Helper method to perform binary search. This method is recursive
* @param array
* @param startIndex
* @param endIndex
* @param element
* @return
*/
private int binarySearchRecursive(int[] array, int startIndex,
int endIndex, int element) {
// check if start index is greater than end index, means
// whole array has been traversed
if (endIndex < startIndex) {
System.out.println("Element not found in array");
return -1;
}
// calculate index of middle element
int middleIndex = (startIndex + endIndex) / 2;
if (array[middleIndex] == element) {
return middleIndex;
}
// check if middle element is less than searched element
if (array[middleIndex] < element) {
// element might be in right sub-array
return binarySearchRecursive(array, middleIndex + 1, endIndex, element);
} else {
// element might be in left sub-array
return binarySearchRecursive(array, startIndex, middleIndex - 1, element);
}
}
public static void main(String[] args) {
// initialize array
int arr[] = { 5, 10, 15, 20, 25, 30 };
// element to search
int element = 30;
int index = new BinarySearch().binarySearchRecursive(arr, key);
if (index != -1) {
System.out.println("Element found at index " + index);
}
}
}
This method also checks the element at the middle position of the array and changes the index of start element and end element accordingly as the middle element is less than or greater than the element to search.
If the index of start element in greater than the index of end element, this means that whole array has been searched and element was not found and thus returns -1 or prints message or both.
Output
Element found at index 5
Method 3: Using Arrays class
java.util.Arrays class has a method binarySearch() which takes an array and element to search as parameters.
It returns the index of element if the element is found otherwise it returns a negative value which is calculated as (-(insertion point) – 1).
Insertion point is the index at which the element should have been present in the array. The array should be sorted in ascending order of elements else the results will be unexpected.
Example,
if the array is { 5, 10, 15, 20, 25, 31 } and we are searching for 30, then its insertion point will be at index 5, thus this method will return (-5 -1) = -6.java.util.Arrays class has overloaded binarySearch() methods which take array of various primitive data types such as long, double, float, char etc., and array of java.lang.Object for custom data types.
import java.util.Arrays;
public class BinarySearch {
private int arraysClass(int[] array, int element) {
int index = Arrays.binarySearch(array, element);
return index;
}
public static void main(String[] args) {
// initialize array
int arr[] = { 5, 10, 15, 20, 25, 30 };
// element to search
int element = 30;
int index = new BinarySearch().arraysClass(arr, element);
if (index != -1) {
System.out.println("Element found at index " + index);
}
}
}
Output
Element found at index 5
Method 4: Using Collections class
java.util.Collections class has a method binarySearch() which takes an object of type java.util.List and an element to be searched in that list.
It returns the index of the searched element in the list if it is found else returns an integer which is calculated as ((-insertion point) – 1) where insertion point is the index where the element would have been present in the list.
The list should be sorted in ascending order of elements else the results will be unexpected.
import java.util.Collections;
import java.util.List;
public class BinarySearch {
private int collectionsClass(Integer[] array, int element) {
// convert array to list
List list = Arrays.asList(array);
int index = Collections.binarySearch(list, element);
return index;
}
public static void main(String[] args) {
// initialize array
Integer arr[] = { 5, 10, 15, 20, 25, 30 };
// element to search
int element = 30;
int index = new BinarySearch().collectionsClass(arr, element);
if (index != -1) {
System.out.println("Element found at index " + index);
}
}
}
Output
Element found at index 5
Hope the methods outlined in the post helped you to understand the concept of binary search and its implementation in java.