Start learning free

LESSON 253 OF 338 · DIVIDE AND CONQUER

Binary Search in Go: Recursive O(log n)

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
    Ctrl + Enter to check

    GO · DIVIDE AND CONQUER

    Binary Search in Go, explained

    Problem overview

    The function find(nums, value) receives a sorted slice of integers and a target. It returns the index where value sits, or -1 when it isn't there. The statement asks for O(log n) time and O(log n) extra space, and for a recursive solution.

    For nums = [1, 2, 4, 5] and value = 4 the answer is 2, because nums[2] is 4.

    Approach: discard half the range at each call

    A linear scan checks every element, which takes O(n). A sorted slice allows something better. Look at the middle element. If it equals value, you are done. If it is smaller than value, everything to its left is smaller still, so the answer can only be in the right half. If it is larger, the answer can only be in the left half. Each comparison throws away half of what remains, so after about log2(n) comparisons the range is empty.

    The recursion works on ranges of one array. Copying half of the slice at each call would cost extra time, so the helper binarySearch takes the bounds left and right and always looks at the same nums. The public function find starts it with the whole slice.

    Here is the search for 4 in [1, 2, 4, 5]. The first call covers indices 0 to 3, and the middle is index 1, which holds 2. That is smaller than 4, so the next call covers indices 2 to 3. Its middle is index 2, which holds 4, so the function returns 2. Searching for 3 in the same slice goes the same way until the call for indices 2 to 3 finds 4 at the middle, which is too large. The next call covers indices 2 to 1, where left > right, and returns -1.

    Step by step

    1. Delegate from find. Return binarySearch(nums, 0, len(nums)-1, value). The helper's result, including -1, is already the final answer.
    2. Declare the helper with the parameters nums []int, left, right and value, returning an int. Go allows the helper to appear after the function that calls it.
    3. Base case. When left > right the range is empty, so the value isn't present: return -1. This is what stops the recursion.
    4. Find the middle index with :=.
    5. Found it. If nums[middle] equals value, return middle.
    6. Middle too small. Recurse on the upper half, from middle + 1 to right, and return the call's result.
    7. Middle too large. Recurse on the lower half, from left to middle - 1, and return that result.

    The solution in Go

    func find(nums []int, value int) int {
    return binarySearch(nums, 0, len(nums)-1, value)
}
func binarySearch(nums []int, left, right, value int) int {
    if left > right {
        return -1
    }
    middle := (left + right) / 2
    if nums[middle] == value {
        return middle
    }
    if nums[middle] < value {
        return binarySearch(nums, middle+1, right, value)
    } else {
        return binarySearch(nums, left, middle-1, value)
    }
}

    Go details:

    • Slices are cheap to pass. A slice value holds a pointer, a length and a capacity, so passing nums into each recursive call copies only that small header, not the elements.
    • Integer division truncates. (left + right) / 2 is a whole number. With non-negative bounds it rounds down, so middle always lies between left and right.
    • Shared type names. left, right, value int declares three int parameters.
    • Every path returns. The last if/else returns in both branches, so Go accepts the function without a trailing return.
    • Overflow. Adding two very large indices could overflow in principle, and left + (right - left) / 2 avoids that. With 64-bit int and slice lengths, the simple average is safe here.

    Complexity

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

    Space: O(log n). No new slices are created, but the recursion keeps one stack frame per active call, and the depth is also about log2(n).

    Edge cases and common mistakes

    • Empty slice. len(nums)-1 is -1, so the first call has left > right and returns -1 without touching nums.
    • One element. The range has left == right, the middle is that element, and the function returns 0 or recurses into an empty range.
    • Using middle instead of middle + 1 or middle - 1. The element at middle has already been ruled out. Keeping it can leave the range unchanged and recurse forever.
    • Forgetting return before the recursive call. The index found deep in the recursion would be dropped, and the function wouldn't compile or would lose the result.
    • Duplicates. The function returns the index of some matching element, not necessarily the first one. In [1, 2, 2, 2, 3] searching for 2 returns 2.
    • Unsorted input. The halving logic relies on order. On an unsorted slice the result can be wrong.

    Testing

    With nums = [1, 2, 4, 5]: searching for 4 returns 2, for 1 returns 0, for 5 returns 3, for 3 returns -1 and for 9 returns -1. With an empty slice, any search returns -1.

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