# Binary Search

Given an an array of

**sorted numbers**, write a function to search a given number in the array.For example, if you're given the following

*sorted*array:arr = [1, 3, 5, 6, 7, 8, 9]

A search for

`7`

should return `True`

, while a search for `2`

should return `False`

.## How Binary Search works

Binary search of a number works on a sorted array by

*removing*half of the array on each step.First we start with the middle number. If the target number is

**greater**than the middle number, then we know the target number is in the left half of the array.Otherwise, our target number is in the right half.

We repeat these steps until we either find our target number

*or*have eliminated the entire array.Step through these steps visually below:

Since the problem is cut in half in each step, the time complexity of binary search is

`O(log(n))`

## Try it

Before you look at the solution, try to implement it yourself.

## Solution

## 5 Essential Sorting & Searching Coding Interview Problems

Master Sorting & Searching by trying the coding challenges below.

- 1.Merge intervalsMedium
- 2.Kth largest in arrayMedium
- 3.Intersection of ArraysMedium
- 4.Search sorted matrixHard
- 5.Search row & col sorted matrixHard