How to implement binary search - Java:
/**
* This class implements binary search.
* @author Juan Antonio Rodríguez
* @version 1.0
*/
public class BinarySearch {
/**
* This method implements binary search.
* @param array array to search.
* @param key key to search.
* @return int Obtains the index of the key in the array.
*/
public int binarySearch(int[] array, int key) {
//Variable to store the index of the key in the array
int index = -1;
//Variable to store the start of the array
int start = 0;
//Variable to store the end of the array
int end = array.length - 1;
//Variable to store the middle of the array
int middle = 0;
//While the start is less than or equal to the end and the index is -1
while (start <= end && index == -1) {
//Calculate the middle of the array
middle = (start + end) / 2;
//If the key is equal to the value in the middle of the array, then set the index to middle
if (key == array[middle]) {
index = middle;
} else {
//If the key is less than the value in the middle of the array, then set the end to middle - 1
if (key < array[middle]) {
end = middle - 1;
} else {
//If the key is greater than the value in the middle of the array, then set the start to middle + 1
if (key > array[middle]) {
start = middle + 1;
}
}
}
}
//Return the index of the key in the array
return index;
}
/**
* One Example
*/
public static void main(String args[]) {
BinarySearch binarySearch= new BinarySearch ();
//Example 1: Search a key in an array with even number of elements
//Array with even number of elements to search a key in it. The elements are sorted in ascending order.
int[] array = {1, 2, 3, 4, 5, 6, 7, 8};
//Key to search in the array. The key is in the array.
int key = 5;
//Search a key in an array with even number of elements.
int index = binarySearch.binarySearch(array, key);
//Output: The index of the key in the array is 4.
System.out.println("The index of " + key + " in " + Arrays.toString(array) + " is " + index);
//Example 2: Search a key in an array with odd number of elements
//Array with odd number of elements to search a key in it. The elements are sorted in ascending order.
int[] array2 = {1, 2, 3, 4, 5, 6, 7};
//Key to search in the array. The key is not in the array.
int key2 = 8;
//Search a key in an array with odd number of elements.
int index2 = binarySearch.binarySearch(array2, key2);
//Output: The index of the key in the array is -1.
System.out.println("The index of " + key2 + " in " + Arrays.toString(array2) + " is " + index2);
}
}
Top comments (0)