Start learning free

LESSON 258 OF 347 · 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: 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

    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