### 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.