DEV Community


Posted on

Binary Search Algorithm

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)

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}
Array of integer values

the index position where a[i] == x or -1 if not found


  1. Define start and range variables
    Start and range variables

  2. Set start to 0, and set range to the length/size of a
    Initialized start and range variables

  3. While start <= range, do the following:

a. Define a mid variable and set it to (start + range)/2 this will get the middle element
Initializing the mid variable

b. If x > a[mid], then set the start variable to mid + 1
if x > a[mid]

else if x < a[mid] set the range variable to mid - 1
if x < a[mid]

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:
value to find

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;
Enter fullscreen mode Exit fullscreen mode

Top comments (2)

adishjain profile image
Adish Jain

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: Would love to hear your thoughts & get your feedback.

tommyc profile image

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.