Start learning free

LESSON 283 OF 414 · DIVIDE AND CONQUER

Binary Search in Scala: Recursive, O(log n) Time

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: the element at index 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 helper function which takes nums, the bounds left and right and value, looks for value in the part of nums between indexes left and right (both included) and returns its index or -1 if not found.

Inside the function, we should compute the middle index mid and compare the element at mid to value. What should we do if:
  • the element at mid is equal to value?
  • the element at mid is less than value?
  • the element at mid is greater than value?

  • If the element at mid is equal to value, then we found our solution and we should return mid
  • If the element at mid is less than value, we should continue the search between indexes mid + 1 and right, i.e. return the result of the recursive call on that range
  • If the element at mid is greater than value, we should continue the search between indexes left and mid - 1, i.e. return the result of the recursive call on that range
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
    Ctrl + Enter to check

    SCALA · DIVIDE AND CONQUER

    Binary Search in Scala, explained

    Problem overview

    The method find receives a sorted Array[Int] called nums and an integer value. It returns the index where value sits, or -1 when the array doesn't contain it. The search has to be recursive and must run in O(log n) time with O(log n) extra space.

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

    Approach: throw away half of the range each time

    Checking every element is O(n). Because the array is sorted, you can do much better. Look at the middle element of the range you are searching:

    • if it equals value, you are done;
    • if it is smaller than value, everything to its left is smaller too, so the answer can only be in the upper half;
    • if it is larger, the answer can only be in the lower half.

    Each comparison discards half of the remaining range. An array of one million elements needs at most about 20 comparisons, because halving a million 20 times leaves nothing. That is where O(log n) time comes from.

    To make this recursive, the function must be able to search just a piece of the array. That is why the lesson adds a helper, binarySearch(nums, left, right, value), whose left and right parameters are the inclusive bounds of the piece. Nothing is copied: every call receives the same array and only the bounds change.

    The recursion needs a base case. When left becomes greater than right, the range is empty, so the value isn't there and the answer is -1.

    Step by step

    1. Delegate from find. The first search covers the whole array, from index 0 to nums.length - 1. Both bounds are inclusive.
    2. Declare the helper with the array, the two bounds and the target, and an Int result.
    3. Write the base case first. If left > right, return -1. Without it the recursion would never stop.
    4. Compute mid as a val: the average of left and right, using integer division.
    5. Check for a hit. If nums(mid) == value, return mid. Scala reads an array element with parentheses, not square brackets.
    6. Go right when the middle is too small. If nums(mid) < value, return the result of searching mid + 1 to right.
    7. Otherwise go left. Return the result of searching left to mid - 1. Using mid - 1 and mid + 1, not mid, matters: mid has just been ruled out, and keeping it could make the range stop shrinking.

    The solution in Scala

    class Solution {
    def binarySearch(nums: Array[Int], left: Int, right: Int, value: Int): Int = {
        if (left > right) {
            return -1
        }
        val mid = (left + right) / 2
        if (nums(mid) == value) {
            return mid
        }
        if (nums(mid) < value) {
            return binarySearch(nums, mid + 1, right, value)
        } else {
            return binarySearch(nums, left, mid - 1, value)
        }
    }

    def find(nums: Array[Int], value: Int): Int = {
        return binarySearch(nums, 0, nums.length - 1, value)
    }
}

    Details worth knowing:

    • Explicit return. Scala normally returns the value of a method's last expression, so return is rarely needed. Here it makes each branch easy to read, and it is allowed because the methods declare their result type (: Int).
    • Integer division. (left + right) / 2 divides two Ints and drops the fraction, so mid is always a valid index in the range. For left = 0 and right = 3 it is 1.
    • Arrays are passed by reference. Passing nums down the recursion costs nothing, no matter how big it is.
    • Returning the recursive result. Each return binarySearch(...) hands the answer found deeper in the recursion straight back to the caller. Dropping the return in the middle of a method would discard that answer.

    Complexity

    Time: O(log n). Each call does a constant amount of work and the range shrinks to at most half its size, so there are at most about log2(n) + 1 calls.

    Space: O(log n). Every call that hasn't returned yet occupies a stack frame, and the recursion is at most that many calls deep. An iterative loop with left and right variables would need only O(1).

    Edge cases and common mistakes

    • Value not present. With [1, 2, 4, 5], searching for 3 returns -1, and so do 0 and 9, which lie outside the array's range.
    • First and last elements. Searching for 1 returns 0 and searching for 5 returns 3. These are the cases that expose a base case written as left >= right, which would skip a range of one element.
    • Empty array. The first call is binarySearch(nums, 0, -1, value). Since 0 is greater than -1 the base case fires and find returns -1.
    • One element. Array(7) searched for 7 returns 0.
    • Duplicates. The method returns the index of some match, not necessarily the first. For Array(2, 2, 2, 2, 2) searching for 2 it returns 2, the middle.
    • Overflow in the midpoint. Int is 32 bits and wraps silently. With left = 1500000000 and right = 2000000000, (left + right) / 2 gives -397483648, because the sum doesn't fit. Writing left + (right - left) / 2 gives the correct 1750000000. Arrays that large are rare, but the second form costs nothing and is a good habit.
    • Unsorted input. Binary search only works on sorted data. On an unsorted array it can return -1 for a value that is present.

    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 = [], value = 7 gives -1.
    • nums = [7], value = 7 gives 0.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free