# Binary Search

Master binary search, the quintessential algorithm for finding elements in a sorted array with logarithmic efficiency.

Searching
easy

Published At

6/4/2021

Write a function that takes in a sorted array of integers as well as a target integer. The function should use the Binary Search algorithm to determine if the target integer is contained in the array and should return its index if it is, otherwise -1.

If you're unfamiliar with Binary Search, we recommend watching the Conceptual Overview section of this question's video explanation before starting to code.

### Sample Input

js
``````array = [0, 1, 21, 33, 45, 45, 61, 71, 72, 73]
target = 33``````
js
``````array = [0, 1, 21, 33, 45, 45, 61, 71, 72, 73]
target = 33``````

### Sample Output

js
``3``
js
``3``

### Hints

Hint 1

The Binary Search algorithm works by finding the number in the middle of the input array and comparing it to the target number. Given that the array is sorted, if this middle number is smaller than the target number, then the entire left part of the array is no longer worth exploring since the target number can no longer be in it; similarly, if the middle number is greater than the target number, then the entire right part of the array is no longer worth exploring. Applying this logic recursively eliminates half of the array until the number is found or until the array runs out of numbers.

Hint 2

Write a helper function that takes in two additional arguments: a left pointer and a right pointer representing the indices at the extremities of the array (or subarray) that you are applying Binary Search on. The first time this helper function is called, the left pointer should be zero and the right pointer should be the final index of the input array. To find the index of the middle number mentioned in Hint #1, simply round down the number obtained from: (left + right) / 2. Apply this logic recursively until you find the target number or until the left pointer becomes greater than the right pointer.

Hint 3

Can you implement this algorithm iteratively? Are there any advantages to doing so?

Optimal Space & Time Complexity

O(log(n)) time | O(1) space - where n is the length of the input array

Solution-1
js
``````function binarySearch(array, target) {
let hello = findTarget(array, 0, array.length - 1, target)
return hello
}

function findTarget(array, first, last, target) {
if (first > last)  return -1;
let middle = Math.floor((first + last) / 2)
if (array[middle] === target) {
return middle;
} else if (target < array[middle]) {
return findTarget(array, first, middle - 1, target);
} else {
return findTarget(array, middle + 1, last, target)
}
}``````
Solution-1
js
``````function binarySearch(array, target) {
let hello = findTarget(array, 0, array.length - 1, target)
return hello
}

function findTarget(array, first, last, target) {
if (first > last)  return -1;
let middle = Math.floor((first + last) / 2)
if (array[middle] === target) {
return middle;
} else if (target < array[middle]) {
return findTarget(array, first, middle - 1, target);
} else {
return findTarget(array, middle + 1, last, target)
}
}``````

🦦

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek 🙏

## Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

• In-depth looks at my covert projects and musings to ignite your imagination.
• Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
• A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.