The theory
A binary search algorithm is a search algorithm that uses the concept of divide and conquer in order to find a target value’s position. Basically, this search algorithm compares the target value with the middle element of the collection.
If it is equal, return the position. If it is not equal, then we will need to check if the value is either greater or less than the target value. This is to know what side of the collection we need to split.
Binary Search Requirements
There’s a condition applied to the binary search array, which is that the array must be sorted. This is because it uses the value (in our case an integer), to compare and check if the selected position has the target value or check where to go.
Implementation
First things first, we will create our binary search class with the search methods.
public class BinarySearch { public int search(int[] array, int number) { return search(array, number, 0, array.length); } private int search(int[] array, int target, int start, int end) { int mid = (start + end) / 2; if (end < start) { return -1; } if (array[mid] == target) { return mid; } else if (array[mid] > target) { return search(array, target, 0, mid - 1); } else { return search(array, target, mid + 1, end); } } }