Start learning free

LESSON 272 OF 414 · BINARY SEARCH

Binary Search in Scala: Searching a Sorted Array in O(log n)

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: the element at index 2 is 4

Note:

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

STEP 1 OF 7
    Ctrl + Enter to check

    SCALA · BINARY SEARCH

    Binary Search in Scala, explained

    What searching means

    Searching is the task of finding where a value sits in a collection, or learning that it isn't there. The simplest method is a linear search: look at the elements one by one from the start until you find the value or run out of elements. On an array of n elements that takes up to n comparisons, so its time is O(n).

    If 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, the target can only be in the right half. If it is too big, the target can only be in the left half. Either way, half of the remaining elements are ruled out with one comparison. Repeating this shrinks the range from n to n / 2, n / 4, and so on until it is empty, so the time is O(log n). An array of a million elements needs about twenty comparisons. The extra space is O(1): just a few integers.

    The problem

    The method find receives a sorted Array[Int] called nums and an Int called value. It returns the index of value in nums, or -1 if the value is not there. For Array(1, 2, 4, 5) and value = 4 the answer is 2, because nums(2) is 4.

    The idea in detail

    Keep two markers, left and right, that bound the part of the array where the value could still be. Both are inclusive: they are indices of elements that haven't been ruled out. At the start, left is 0 and right is nums.length - 1.

    Each round, compute the middle index and compare:

    • If nums(middle) equals value, return middle.
    • If it is smaller, everything at or before middle is too small, so move left to middle + 1.
    • Otherwise it is bigger, so everything at or after middle is too big and right moves to middle - 1.

    When left passes right, no candidates remain, and the answer is -1.

    Searching for 4 in Array(1, 2, 4, 5): left is 0 and right is 3, so middle is 1 and nums(1) is 2. That is smaller than 4, so left becomes 2. Now the middle is 2 + (3 - 2) / 2 = 2, and nums(2) is 4, a match. The method returns 2.

    Step by step

    1. Declare the markers left and right with var, because both change in the loop. They start at 0 and nums.length - 1.
    2. Loop while the range is non-empty: while (left <= right). Use <=, not <: when the two are equal, one element is still unchecked.
    3. Compute the middle as a val: left + (right - left) / 2. Dividing two Int values truncates, so there is no rounding to do.
    4. Found it. If nums(middle) == value, return middle. Arrays are indexed with parentheses in Scala.
    5. Too small. If nums(middle) < value, set left = middle + 1. The element at middle has been ruled out, so skip it.
    6. Too big. Otherwise set right = middle - 1, for the same reason.
    7. Not found. After the loop, return -1.

    The solution in Scala

    class Solution {
    def find(nums: Array[Int], value: Int): Int = {
        var left = 0
        var right = nums.length - 1
        while (left <= right) {
            val middle = left + (right - left) / 2
            if (nums(middle) == value) {
                return middle
            } else if (nums(middle) < value) {
                left = middle + 1
            } else {
                right = middle - 1
            }
        }
        return -1
    }
}

    Scala details and gotchas

    • Why not (left + right) / 2. Int in Scala is 32 bits and overflow wraps silently. With left = 1500000000 and right = 2000000000, the sum 3500000000 doesn't fit and the expression gives -397483648, a negative index. left + (right - left) / 2 gives 1750000000. The difference right - left can't overflow here, because it is never larger than right. For real arrays, which are far smaller than two billion elements, both forms work, but the safe one is a good habit.
    • Integer division truncates. 7 / 2 is 3. For non-negative numbers that means the middle of an even-sized range is the left one of the two central elements.
    • Return inside while. The return middle sits in a while loop in the method body, so it simply leaves the method. Scala allows the final return -1, or you could write just -1 as the last expression.
    • Empty array. With nums.length == 0, right starts at -1, the loop condition 0 <= -1 is false, and the method returns -1 without indexing the array.
    • Several equal values. If the value appears more than once, the method returns the index of one of them, not necessarily the first.

    Common mistakes

    • Using left < right. A range of exactly one element is never checked, so Array(1, 2, 4, 5) with value 5 could be reported as missing.
    • Setting left = middle or right = middle. The element at middle has already been compared. Keeping it lets the range stop shrinking, and the loop can run forever. For example, when left equals middle, left = middle changes nothing.
    • Running it on an unsorted array. The discard logic depends on the order. On unsorted data the method can discard the half that holds the value.
    • Putting the -1 inside the loop. The -1 belongs after the loop. Reaching it means every candidate was discarded.

    Testing

    • Array(1, 2, 4, 5), value 4 gives 2.
    • Array(1, 2, 4, 5), value 1 gives 0, and value 5 gives 3.
    • Array(1, 2, 4, 5), value 3 gives -1, and value 9 gives -1.
    • Array(), 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 inclusive bounds, loop with left <= right, and move the bounds to middle + 1 or middle - 1.
    • Compute the middle as left + (right - left) / 2 to avoid Int overflow.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free