JavaScript: Binary Search Algorithm
Explained With a Problem From LeetCode
For today’s algorithm, I picked the binary search which is one of the most commonly asked topics in technical interviews. The problem named binary search from LeetCode will be used to explain this concept:
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.
Example 1:Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
While linear searching checks every single element one at a time and works in a sorted or unsorted piece of data, binary searching eliminates half of the remaining elements at a time and works only on sorted data. The basic idea behind this technique is to find a certain element in a sorted sequence using a divide and conquer approach. This algorithm allows us to quickly find the position of a target value within a sorted list basically by reducing the search area by half at each iteration and it is usually faster than linear search for large amounts of data. We will use iterative binary search technique to solve the given question and here is a visual representation of our approach:
