Get current working directory

Binary Search Implementation using Java

Let's write a source code for binary search in Java. There are many ways we can write logic for binary search:

1. 
   Iterative implementation
   
2. 
   Recursive Implementation
   
3. 
   Using Arrays.binarySearch()
   
4. 
   Using Collections.binarySearch()
   

Iterative Implementation

public class BinarySearch {

public int binarySearchIteratively(int[] sortedArray, int key) {

int low = 0;
int high = sortedArray.length - 1;
int index = Integer.MAX_VALUE;

while (low <= high) {

int mid = (low + high) / 2;

if (sortedArray[mid] < key) {

low = mid + 1;
} else if (sortedArray[mid] > key) {
high = mid - 1;
} else if (sortedArray[mid] == key) {
index = mid;
break;
}
}
return index;
}

public static void main(String[] args) {

int[] sortedArray = { 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 };
int key = 6;
BinarySearch binSearch = new BinarySearch();
int index = binSearch.binarySearchIteratively(sortedArray, key);
System.out.println("Search element found " + key+ " in location index : " + index);
}
}
Output:
Search element 6 found in location index : 7
The binarySearchIteratively method takes a sortedArray, key & the low & high indexes of the sortedArray as arguments. When the method runs for the first time the low, the first index of the sortedArray, is 0, while the high, the last index of the sortedArray, is equal to its length – 1.
The middle is the middle index of the sortedArray. Now the algorithm runs a while loop comparing the key with the array value of the middle index of the sortedArray.

Recursive Implementation

Now, let’s have a look at a simple, recursive implementation as well:

public class BinarySearch {

public int binarySearchRecursively(int[] sortedArray, int key, int low, int high) {

int middle = (low + high) / 2;

if (high < low) {
return -1;
}

if (key == sortedArray[middle]) {

return middle;
} else if (key < sortedArray[middle]) {
return binarySearchRecursively(sortedArray, key, low, middle - 1);
} else {
return binarySearchRecursively(sortedArray, key, middle + 1, high);
}
}

public static void main(String[] args) {

int[] sortedArray = { 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 };
int key = 6;
BinarySearch binSearch = new BinarySearch();
int index = binSearch.binarySearchRecursively(sortedArray, key, 0, sortedArray.length -1);
System.out.println("Search element found in location index : " + index);
}
}
Output:
Search element found in location index : 7
The binarySearchRecursively method accepts a sortedArray, key, the low and high indexes of the sortedArray.