Start learning free

LESSON 259 OF 348 · DIVIDE AND CONQUER

Binary Search in TypeScript: Recursive O(log n) Version

Practice Recursive Read the full explanation

Implement a recursive Binary Search algorithm that given a sorted array of integers nums, finds and returns the index of a given value.

If the value doesn't exist in nums, return -1.

Example 1:

Input: nums = [1, 2, 4, 5], value = 4
Output: 2
Explanation: nums[2] is 4

Note:

Your algorithm should run in O(log n) time and use O(log n) extra space.

Hints:

Since our subproblems reduce to searching the value in a subarray, we will write a recursive function binarySearch(nums, left, right) which looks for value in nums[left...right] and returns its index or -1 if not found.

Inside the function, we should compute the middle index mid and compare nums[mid] to value. What should we do if:

a[mid] is equal to value?
a[mid] is less than value?
a[mid] is greater than value?

If a[mid] is equal to value, then we found our solution and we should return mid
If a[mid] is less than value, we should continue the search in nums[mid + 1...right], e.g. return binarySearch(nums, mid + 1, right)
If a[mid] is greater than value, we should continue the search in nums[left...mid - 1], e.g. return binarySearch(nums, left, mid - 1)

When should the function return -1 tho?

At the start of the function, we should treat the base case: left > right. This means we reduced the searching area to an empty subarray, so there is no solution and we should return -1

STEP 1 OF 7

Guided

Ctrl + Enter to check

TYPESCRIPT · DIVIDE AND CONQUER

Binary Search in TypeScript, explained

Problem overview

The method find receives a sorted array of integers, nums, and a value. It returns the index of value in nums, or -1 if it isn't there. This lesson asks for the recursive form of binary search, with O(log n) time and O(log n) extra space.

In the example, nums = [1, 2, 4, 5] and value = 4. The 4 is at index 2, so the answer is 2.

Approach: halve the range, recurse on one half

Scanning the array takes O(n). Because the array is sorted, one comparison with the middle element rules out half of it:

if the middle element equals value, return its index;
if it is smaller than value, the target can only be to the right;
if it is larger, the target can only be to the left.

Searching one half is the same problem again on a smaller range, which makes it a natural fit for recursion. The range is described by two indices, left and right, so the array is never copied. When left passes right, the range is empty and the value is not there.

For [1, 2, 4, 5] and value = 4: the first call has left = 0 and right = 3, so mid = 1 and nums[1] = 2 is smaller than 4. The next call has left = 2 and right = 3, so mid = 2 and nums[2] = 4. It returns 2.

A missing value shows the base case at work. For value = 3 in the same array, the first call has mid = 1 and nums[1] = 2, smaller than 3, so the range becomes 2 to 3. There mid = 2 and nums[2] = 4, larger than 3, so the range becomes 2 to 1. That range is empty, left > right holds, and the call returns -1. The two outer calls pass that -1 upward unchanged.

The same algorithm can be written with a while loop and no recursion. The recursive form is worth learning because many other problems split in the same way: solve a smaller instance, then use or pass along its answer. Here the "combining" step is trivial, since each call just returns what the deeper call returned.

Step by step

Delegate from find. It calls this.binarySearch(nums, 0, nums.length - 1, value) and returns the result, searching the whole array.
Declare the helper above find, taking the array, the left and right bounds and the value, and returning number. The bounds as parameters let each call work on a smaller range of the same array.
Write the base case. If left > right, return -1. Without it the recursion would not stop.
Compute mid as Math.floor((left + right) / 2). The division can give a fraction, such as 2.5, and an index must be a whole number.
Found it. If nums[mid] == value, return mid.
Too small. If nums[mid] < value, return the result of the same method with mid + 1 as the new left bound.
Too large. Otherwise return the result of the same method with mid - 1 as the new right bound.

The solution in TypeScript

class Solution {
    binarySearch(nums: number[], left: number, right: number, value: number): number {
        if (left > right) {
            return -1;
        }
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] == value) {
            return mid;
        }
        if (nums[mid] < value) {
            return this.binarySearch(nums, mid + 1, right, value);
        } else {
            return this.binarySearch(nums, left, mid - 1, value);
        }
    }

    find(nums: number[], value: number): number {
        return this.binarySearch(nums, 0, nums.length - 1, value);
    }
}

Some TypeScript details:

Division does not round. A number is a double, so (0 + 3) / 2 is 1.5. Reading nums[1.5] gives undefined, so Math.floor is required.
No overflow in the midpoint. In languages with 32-bit integers, left + right can overflow for huge arrays. A double has no such problem for array indices, so the simple sum is safe.
Return the recursive result. Writing this.binarySearch(...) without return discards the answer, and the method would give back undefined (with the lessons' compiler settings, tsc does not report this, so the bug is easy to miss).
Calls go through this. find and the helper are methods of the class.
The number annotations are erased when the code is compiled to JavaScript. They check nothing while the program runs.

Complexity

Time: O(log n). Each call halves the range, and does a constant amount of work. An array of a million elements needs about 20 calls.

Space: O(log n). Every pending call occupies a frame on the call stack, and the depth is the number of halvings. A loop-based version uses O(1) space, which is the usual comparison between the two forms.

Edge cases and common mistakes

Empty array. The first call has left = 0 and right = -1, so it returns -1 immediately.
Value missing. For [1, 2, 4, 5] and value = 3 the range shrinks until left passes right, and the method returns -1.
Value at either end. The first and last elements are found like any other. In [1, 2, 4, 5], the value 1 gives 0 and the value 5 gives 3.
mid instead of mid + 1 or mid - 1. The middle element has already been ruled out. Keeping it in the range can make a call repeat itself forever.
Using left >= right as the base case. A range with one element would be skipped, and a present value would be reported as missing.
Unsorted input. The method gives wrong answers without any error.
Duplicates. If the value occurs several times, the method returns the index of one of them, not necessarily the first.

Testing

nums = [1, 2, 4, 5], value = 4 gives 2.
The same array with value = 3 gives -1.
The same array with value = 1 gives 0, and with value = 5 gives 3.
nums = [], value = 1 gives -1.
nums = [1], value = 1 gives 0.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free