Binary search is a very powerful algorithm for finding results on datasets of any size. Though, with such performance comes also one important required for it to work properly: the list must be sorted. Another fundamental requirement is knowing the number of items within said list, but in JavaScript-land this is a given.
How it works
The mechanism is quite simple actually: the array
is broken into 2 halves, which leads the program with 2 range of sorted values (already half of the size of initial set). Now, the program checks into which range of values the target value belongs.And, subsquentially it executes again until the searched value is on either end of the array
.
The code
Let's see how a Binary Search could be implemented in Typescript:
-
list
: the sortedarray
. -
value
: the target value to be found. -
start
: theindex
in which the current iteration shall commence. stop
: theindex
in which the current iteration shall terminate.@return
: the index of the found target
const binarySearch = (
list: number[],
value: number,
start = 0,
stop: number
):number {
// `start` can be defined, but will default to `0`
// as it is the first defined value of any array
// if undefined, `stop` becomes the index of the last item
stop = stop || list.length - 1
// `middle` is the mean between `start` and `stop`
const middle = Math.floor((start + stop) / 2)
// if middle is not the target value
if (list[middle] === value) return middle
if (value < list[middle]) {
// defines the `stop` value for the next iteration
stop = middle - 1
} else {
// defines the `start` value for the next iteration
start = middle + 1
}
// binarySearch calls itself again with the newly set values
return binarySearch(list, value, start, stop)
}
thanks Curtis Fenner for the improvement suggestions!
Shameless plug
I have a personal playground where I plan to implement some Computer Science basics in JavaScript. With good test coverage and some insights on when/why to use each concept. Check out my binary search implementation at the FUNdamentals repository.
Top comments (2)
There's a few things that can make this code much nicer.
First, there's no reason to make
middle
be a parameter. Notice how you're computing it the same way in two different places?Second, an "early return" will eliminate the nesting, making the logic much simpler -- although you could also replace the recursion with a
while
loop.Thank you, Curtis.
I updated the code with some of your suggestions 🙂