# JavaScript: Find a Number in an Ordered Array

Here is a common JavaScript interview question:

**Given an array of n integers sorted in ascending order, how quickly can we find if a given integer is in the array?**

There are three ways to solve it that I can think of.

## Cheating!

The new includes() method makes this quite simple.

```
const arr = [1,2,3,4,5];
arr.includes(2); // true
arr.includes(7); // false
```

But let’s assume we can’t use this approach.

## Brute Force

We can iterate through the entire array to find our integer. This takes `O(n)`

time in the worst case.

```
// O(n) time & O(1) space
function findNum(arr, n) {
for (let i=0; i<arr.length; i++){
if (arr[i] === n) {
return true;
}
}
return false;
}
```

## Binary Search

If the list was **not sorted** we could solve this in `O(n log n)`

time by first sorting the list `O(log n)`

and then iterating over it `O(n)`

.

But it’s already sorted! So we can use binary search to solve this in `O(log n)`

time.

How does binary search work again?

- Start with the middle number mid. If n > mid then return the section of the array larger than mid. Otherwise return the section less than mid.
- We’ve cut our problem size in half!
- Repeat this approach of starting in the middle and dividing the remaining array into half under we find the number or determine it’s not in the array.

```
// O(log n) time & O(1) space
function binarySearch(arr, n) {
let min = 0,
max = arr.length - 1,
guess;
while (min <= max) {
guess = Math.floor((min + max) / 2);
if (arr[guess] === n) {
return true;
} else {
if (arr[guess] < n) {
min = guess + 1;
} else {
max = guess - 1;
}
}
}
return false;
}
```

**Want to improve your JavaScript? I have a list of recommended JavaScript books.**