In Chapter 13, Sorting and Searching Algorithms, we learned how to implement the binary using an iterative approach. If we go back and take a look at the algorithm, we can use the divide and conquer approach to implement the binary search as well. The logic is the following:
- Divide: Calculate mid and search lower or upper half of the array
- Conquer: Search value in the lower or upper half of the array
- Combine: Not applicable as we are returning the index directly
The divide and conquer binary search algorithm is the following:
function binarySearchRecursive( array, value, low, high, compareFn = defaultCompare) { if (low <= high) { const mid = Math.floor((low + high) / 2); const element = array[mid]; if (compareFn(element, value) ...
