Binary Search is an algorithm that is used to search an element in a sorted array. Yes, the array needs to be sorted in order for the Binary Search algorithm to work.
How does it work?
Let's think of a real-world example, a phone book. Let's say you wanted to call your friend, Val. You know your phone book is sorted in alphabetical order, so you start searching for the letter 'v'. Most people would take the following steps:
1) you open the phone book somewhere in the middle.
2) you land in a specific section, such as the letter 'n'.
3) you know that the letter 'v' comes after the letter 'n', therefore any pages before 'n' will be ignored. You will then go to the middle section between letters 'n' and 'v'.
4) you end up in the 't' section.
5) you know that the letter 't' comes before 'v', so any pages before the letter 't' will be disregarded. You will then flip to the middle section between letters 't' and 'v'.
And so on..Until you find the correct section.
Ultimately, you are using a binary search algorithm to navigate through the phone book. You find the mid point by breaking the list in half, compare your search target to the mid point, disregard one of the halves depending on where the target is most likely to be found, then continue the search in the other half by repeating the process. We apply the same logic when searching for an element in a sorted array.
Let's take a look at the following challenge:
Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Our goal is to write an algorithm which will search the given array to find the target. We can traverse through the array in O(n) time where n is the length of the array. However, our goal here is to get the time complexity less than O(n) and that is O(log(n)) time. We can achieve this by solving the problem recursively.
How does this algorithm work?
1) Let's define our binary search function binarySearch that takes in an array and a target. In our case, nums = [-1,0,3,5,9,12] and target = 9.
2) Just like in our phone book example, we first need to break this array in two halves. We can do this by finding the middle index.
3) To find the middle index we will first set our left and right pointers (I'll call them lo and hi). This will also help us track the left and right bounds of the array. Let's add lo and hi as arguments and set lo to 0 and hi to nums.length - 1).
4) Before we continue, we should set our base case. Our function will return -1 when our left pointer is greater than the right pointer. In other words, we are done once the left pointer surpasses the right one.
5) We then calculate the middle index using Math.floor((lo + hi)) / 2 ). We use Math.floor to round the number down. Let's call it middle. In our case, our middle index will be equal to 2.
6) Once the middle index is found, we can now start comparing our target to nums[middle].
7) Let's do the first comparison. Our target (9) is greater than nums[middle] which is 3. It means that we can disregard all the numbers before our middle index because we know that those numbers are going to be smaller. We can do this by moving our lo pointer to the index right after our middle index. We return another call to our binarySearch function where we now pass in a different left pointer (middle + 1).
8) We then repeat the process. Once the target is found, our function will return the middle index.
Top comments (0)