What is Binary search?
Binary search is an algorithm that solves search problems, and its input is a sorted list of elements. If an element you’re looking for is in that list, it returns the position where it’s located. Otherwise, binary search returns -1 or null
Suppose you’re searching for a word that starts with letter M in a dictionary. You could start at the beginning and keep flipping pages until you get to the Ms. But you’re more likely to start at a page in the middle, because you know the Ms are going to be near the middle of the dictionary. In general, for any list of n, binary search will take O(log n) steps to run in the worst case, whereas simple search will take n steps.
Psuedocode w/ illustrations
Name of method:
binarySearch(a, x)
Inputs:
a: The sorted array to search in
x: The value we are searching for in a
As an example we'll use int[]{11, 88, 99, 111, 223, 999, 1028}
Outputs:
the index position where a[i] == x or -1 if not found
Procedures:
While start <= range, do the following:
a. Define a mid variable and set it to (start + range)/2 this will get the middle element
b. If x > a[mid], then set the start variable to mid + 1
else if x < a[mid] set the range variable to mid - 1
c. if a[mid] = x, then return mid
4.Return -1 if the value isn't found
Sample code:
Let's find the index position of:
public class MyClass {
public static void main(String[] args) {
System.out.print(binarySearch( new int[]{11, 88, 99, 111, 223, 999, 1028}, 999 ));
}
public static int binarySearch(int[] a, int x){
int start = 0;
int range = a.length-1;
while(start <= range){
int mid = (start + range) / 2;
if(x > a[mid]) start = mid + 1;
else if(x < a[mid]) range = mid - 1;
else return mid;
}
return -1;
}
}
Top comments (2)
Hey Tommy! Awesome post. I couldn't find how to contact you, but I wanted to share this interactive tutorial I wrote on Binary Search: getleaf.app/dsps301/binarysearch-k.... Would love to hear your thoughts & get your feedback.
Hi Adish,
Excellent article about Binary Search! You seemed to hit on every point really well. I like the feature where you see the visual explanations as you step into the code line by line.