Start learning free

LESSON 282 OF 413 · DIVIDE AND CONQUER

Binary Search in C#: 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: 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

    C# · DIVIDE AND CONQUER

    Binary Search in C#, explained

    Problem overview

    Find receives a sorted int[] nums and an int value. It returns the index of value in the array, or -1 if the value isn't there. This lesson requires a recursive implementation. For nums = {1, 2, 4, 5} and value = 4, the answer is 2, because nums[2] is 4.

    The lesson asks for O(log n) time and O(log n) extra space. The time comes from halving the search area at every step. The space comes from the recursion: each call waits on the call stack for the next one.

    Approach: one smaller search per call

    Searching the whole array for a value is the same job as searching a part of it. That suggests a helper that looks only at the slice nums[left..right] and calls itself on a smaller slice. Find then starts it on the entire array.

    Look at the middle element mid of the slice and compare it to value:

    • If they are equal, the search is over: return mid.
    • If nums[mid] is smaller than value, the array is sorted, so the value can only be to the right. Search mid + 1..right.
    • If nums[mid] is larger, the value can only be to the left. Search left..mid - 1.

    The base case is an empty slice, when left > right. Nothing is left to look at, so the value isn't in the array, and the result is -1.

    Here is a search for 3 in {1, 2, 4, 5}, which is absent. The first slice is indices 0 to 3, and mid is 1, with value 2. It is smaller than 3, so the search continues in 2 to 3. There mid is 2, with value 4, which is larger, so the search continues in 2 to 1. That slice is empty, and the result is -1.

    Step by step

    1. Delegate from Find. Find returns BinarySearch(nums, 0, nums.Length - 1, value), the helper's result for the whole array. The helper's answer, -1 included, is already the final one.
    2. Declare the helper above Find as public int BinarySearch(int[] nums, int left, int right, int value). The bounds are parameters so that each call narrows the range of the same array. C# arrays are reference types, so passing nums to every call doesn't copy it.
    3. Add the base case. If left > right, return -1. Without it, the recursion would keep going until the call stack overflowed.
    4. Compute mid as (left + right) / 2. Integer division truncates, so no rounding call is needed.
    5. Check for a match. If nums[mid] == value, return mid.
    6. Go right when the middle is too small. If nums[mid] < value, return BinarySearch(nums, mid + 1, right, value).
    7. Otherwise go left and return BinarySearch(nums, left, mid - 1, value). It must be mid - 1, not mid: mid has been ruled out already, and keeping it could recurse forever.

    The solution in C#

    class Solution {
    public int BinarySearch(int[] nums, int left, int right, int value) {
        if (left > right) {
            return -1;
        }
        int 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);
        }
    }

    public int Find(int[] nums, int value) {
        return BinarySearch(nums, 0, nums.Length - 1, value);
    }
}

    C# details worth knowing

    • The result must be returned. Both recursive calls are written as return BinarySearch(...). A recursive call only produces a value, and the index found deep in the recursion has to travel back up through every caller. Dropping a return loses it, and C# reports an error because not every path returns a value.
    • Integer division. With int operands, (0 + 3) / 2 is 1. The fraction is dropped, which is the rounding that binary search wants.
    • Midpoint overflow. left + right is computed in int, and C# overflow is silent by default. For indices near the top of the int range the sum would wrap to a negative number. The safe form is left + (right - left) / 2. Arrays of that size are rare, but it is a good habit.
    • Same name as a library method. The Array class has a static method named BinarySearch too, with a different signature. The helper here belongs to Solution, so calling BinarySearch(...) inside the class refers to this one.
    • Ported code. Code written for Java often uses nums.length and a lowercase binarySearch. In C# the size is nums.Length, and the name must match the declaration's casing.

    Complexity

    Every call either returns or searches a slice about half as long as the one before. Starting from n elements, the slice reaches empty after about log₂ n halvings. Each call does a constant amount of work, so the time is O(log n).

    Each call that is still waiting uses one stack frame, and there are about log₂ n of them at the deepest point, so the extra space is O(log n). An iterative version with a loop would need only O(1) space.

    Edge cases and common mistakes

    • An empty array. nums.Length - 1 is -1, so the first call has left = 0 and right = -1. The base case catches it and the method returns -1.
    • Value smaller or larger than everything. The slice shrinks toward one end until it is empty, and the result is -1.
    • Recursing on mid instead of mid + 1 or mid - 1. A slice that doesn't shrink makes the method call itself forever.
    • Searching an unsorted array. The reasoning "the value can only be on the right" requires sorted data. On an unsorted array, the result can be wrong.
    • Duplicates. If the value appears several times, this method returns the index of one of them, whichever the halving reaches first, not necessarily the first.

    Testing

    numsvalueresult
    {1, 2, 4, 5}42
    {1, 2, 4, 5}3-1
    {} (empty)3-1
    {1, 3, 5, 7, 9, 11, 13, 15}136
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free