Java - Binary Search Algorithm

We studied about Linear Search Algorithm in previous post. Linear search don't required the list to be in sorted order. Linear search is a good options for small and unsorted collection. But If the collection size increases linear search is not the ideal search algorithm to use. Binary search is better option for larger collections. One thing required in binary search is the collection must be in sorted order.

Binary Search

Binary search works on divide ans conquer technique, where problem is divided in smaller parts and solved. In binary search the given collection must be in sorted order always. Steps to perform binary search on a given array A to search key are - 

• Find the middle element of A and match with key. If key matches return the index as result.
• If key is less than middle element take the first half otherwise take the second half and perform the same steps.
• If array size reached to zero, return "Element not present in array".  

Binary search reduced the problem(Array) size to half with each step. That's why binary search works efficiently for larger size data also.

Binary search algorithm can be implemented in iterative or recursive manner. I am using iterative methods for this tutorial, you can try with recursive manner for your practice.

Pseudocode - 

# Input: Array elements, Integer size, Integer keyToSearch
# Output: first index of keyToSearch in elements, or -1 if not found
   Set startIndex = 1
   Set endIndex = n
   while keyToSearch not found 
      if startIndex < endIndex 
         return -1.
      set midPoint = startIndex + ( endIndex - startIndex ) / 2
      if A[midPoint] < keyToSearch
         set startIndex = midPoint + 1
      if A[midPoint] > keyToSearch
         set endIndex = midPoint - 1 
      if A[midPoint] = keyToSearch 
         return midPoint.
   End while loop. 
   

Asymptotic Analysis of Binary Search Algorithm -

Best Case Scenario - If the required element is the middle element in the collection and found in first step. Best case time complexity for binary search is O(1).

Worst Case Scenario - If the required element not present in the collection or found in last iteration. Worst case time complexity for binary search is O(log n).

Complexity - Complexity of binary search algorithm is O(log N). The time taken by algorithm to search an element will increase in logarithmic manner with the number of elements in the list.

Binary Search Implementation(Iterative) in Java  -

package javaprinciples.dsa;

public class BinarySearch {

public static int binarySearch(int[] elements, int keyToSearch) {

int startIndex = 0;

int endIndex = elements.length - 1;

while (startIndex <= endIndex) {

int midPoint = startIndex + (endIndex - startIndex) / 2;

if (keyToSearch == elements[midPoint]) {

return midPoint;

}

if (keyToSearch < elements[midPoint]) {

endIndex = midPoint - 1;

} else {

startIndex = midPoint + 1;

}

}

return -1;

}

public static void main(String[] args) {

int[] elements = { 2, 3, 5, 6, 7, 8, 10, 12, 14 };

int keyToSearch = 8;

int keyFoundAt = binarySearch(elements, keyToSearch);

if (keyFoundAt == -1) {

System.out.println("Key " + keyToSearch + " not found in list.");

} else {

System.out.println("Key " + keyToSearch + " found at index: " + keyFoundAt);

}

}

}

Output -

Key 8 found at index: 5

This is all about Binary Search algorithm and its implementation in Java. I hope you liked the post. Feel free to put comments.