LESSON 248 OF 348 · BINARY SEARCH

Binary Search in TypeScript: Searching a Sorted Array

Lesson O(log n) Read the full explanation

In this video lesson we will learn about the concept of searching, linear searching and more important - Binary Searching:

Problem:

Given a sorted array of integers nums, use Binary Search to find and return 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(1) extra space.

STEP 1 OF 7

Guided

Ctrl + Enter to check

Binary Search in TypeScript, explained

Linear search and binary search

Searching means finding where a value sits in a collection, or learning that it is not there. The simplest way is linear search: look at the elements one after another until you find the value or run out. In an array of n elements that takes up to n steps, O(n).

When the array is sorted, you can do far better. Binary search looks at the middle element and compares it with the target. If the middle element is too small, everything to its left is too small as well, so that half can be thrown away. If it is too big, the right half goes. Each comparison halves the range that can still hold the target, so an array of a million elements needs at most about 20 comparisons. The time is O(log n), and the extra space is O(1), since only a few indices are kept.

The whole method depends on the order. On an unsorted array, "the left half is too small" means nothing, and the search can miss values that are present.

The lesson's task

The method find receives a sorted array of integers, nums, and a value. It returns the index where value sits, or -1 if it is missing. For nums = [1, 2, 4, 5] and value = 4 the answer is 2, because nums[2] is 4.

Building it step by step

Keep two markers. left is 0 and right is nums.length - 1, and both are inclusive: they point at elements that may still hold the target. They are declared with let, since the loop moves them.
Loop while the range is not empty. The condition is left <= right. When the two are equal, one element remains and still has to be checked, which is why < would be a bug.
Pick the middle. Math.floor(left + (right - left) / 2) is the index halfway between the markers. In TypeScript, / on numbers keeps the fraction (7 / 2 is 3.5), and an array index must be a whole number, so Math.floor rounds down.
If the middle element equals value, return middle at once.
If the middle element is smaller, the target can only be to the right. Move left to middle + 1.
Otherwise it is bigger, so move right to middle - 1.
If the loop ends, the range emptied without a match. Return -1 after the loop.

class Solution {
    find(nums: number[], value: number): number {
        let left = 0, right = nums.length - 1;
        while (left <= right) {
            let middle = Math.floor(left + (right - left) / 2);
            if (nums[middle] == value) {
                return middle;
            } else if (nums[middle] < value) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return -1;
    }
}

A trace

Searching for 4 in [1, 2, 4, 5]: left = 0, right = 3, so middle = Math.floor(1.5) = 1. The element there is 2, which is smaller than 4, so left becomes 2. Now middle = Math.floor(2 + 0.5) = 2, and nums[2] is 4. The method returns 2.

Searching for 3 in the same array: the first step is the same and sets left = 2. Then middle = 2 and nums[2] is 4, which is bigger, so right becomes 1. Now left > right, the loop ends, and the method returns -1.

TypeScript details

Why middle + 1 and middle - 1. The element at middle has been compared and ruled out. Keeping it in the range could make the loop run forever, for example when left equals middle.
The middle formula. left + (right - left) / 2 equals (left + right) / 2. In languages with fixed-size integers the first form avoids an overflow in left + right. A TypeScript number is a double, so overflow is not a practical worry for array indices, but the form is a good habit.
No integer division. There is no // operator, and / never truncates. Forgetting Math.floor gives an index like 1.5, and nums[1.5] is undefined, which silently makes every comparison false.
Types do not check the order. Nothing in number[] says the array is sorted. If it is not, the method runs without any error and may return the wrong answer.
Numbers, not strings. The comparison nums[middle] < value is numeric because both are numbers. Comparing two strings would use alphabetical order, so "10" < "9" is true.

Common mistakes

Using left < right. The last remaining element is never examined. find([7], 7) would return -1.
Setting left = middle or right = middle. The range may stop shrinking, and the loop never ends.
Returning -1 inside the loop. It must come after the loop. Inside, it would stop the search after one comparison.
Duplicates. If the value appears several times, the method returns one of its indices, not necessarily the first.
Empty array. Then right is -1, the condition is false at once and the method returns -1.

Testing

nums = [1, 2, 4, 5], value = 4 gives 2.
nums = [1, 2, 4, 5], value = 3 gives -1.
nums = [1, 2, 4, 5], value = 1 gives 0, and value = 5 gives 3.
nums = [7], value = 7 gives 0.
nums = [], value = 3 gives -1.

Key takeaways

Binary search needs a sorted array and runs in O(log n) time with O(1) extra space.
Keep an inclusive range, loop while left <= right, and always move past middle.
Round the middle down with Math.floor, because TypeScript has no integer division.

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

Start learning free