Searching algorithms

Table of Contents

Binary search

Prerequisite: The array has to be ordered.

Searches the array anArray[ﬁrst] through anArray[last] for a given value by using a binary search.

With the recursive method, we pass lo and hi into the method. So the only calculation we have to do in the method is for mid.

With the iterative method, we first calculate low and high, and then start a loop, and then change the values of low and high inside the loop.

The mid point calculation caused out of bounds errors for modern large sized datasets.

var mid = Math.floor(low + high) / 2);         // bad

var mid = low + Math.floor((high - low) / 2);  // good