LESSON 247 OF 347 · BINARY SEARCH

Binary Search in C#: Finding a Value in a Sorted Array

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: nums[2] is 4

Note:

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

STEP 1 OF 7

Guided

Ctrl + Enter to check

C# · BINARY SEARCH

Binary Search in C#, explained

What searching means

Searching is the task of finding where a value sits in a collection, or learning that it is not there. The simplest method is the linear search: look at the elements one by one from the start until you find the value or reach the end. For an array of n elements that takes up to n steps, so it is O(n).

If the array is sorted, you can do far better. Binary search compares the target with the middle element and, based on that one comparison, throws away half of the remaining range. Repeating this halves the range again and again, so it needs about log₂ n steps: roughly 20 comparisons for a million elements, and about 30 for a billion.

The idea

Keep two indices, left and right, that mark the part of the array that could still contain the target. Both are inclusive. At each step look at the middle element:

If it equals the target, return its index.
If it is smaller than the target, everything at or before the middle is also too small, because the array is sorted. Continue in the right half.
If it is larger, everything at or after the middle is too large. Continue in the left half.

When the range becomes empty, the target is not in the array.

For nums = [1, 2, 4, 5] and value = 4: the range is indices 0 to 3, and the middle is index 1, holding 2. That is smaller than 4, so the range becomes indices 2 to 3. The middle is index 2, holding 4, which matches, so the answer is 2.

The exercise, step by step

The method Find(int[] nums, int value) returns the index of value in the sorted array nums, or -1 when it is missing. The statement asks for O(log n) time and O(1) extra space.

Set up the bounds. left starts at 0 and right at nums.Length - 1, the last index. Both are inclusive, and arrays report their size through the Length property.
Loop while left <= right. The range holds at least one element as long as left has not passed right. With < instead, the last remaining element would never be checked.
Compute middle. left + (right - left) / 2 is the index halfway between them. Dividing two int values in C# truncates, so no rounding call is needed.
Found it. If nums[middle] == value, return middle.
Too small. If nums[middle] < value, set left = middle + 1. The element at middle is already ruled out, so skip past it.
Too big. Otherwise set right = middle - 1, for the same reason.
Not found. After the loop, return -1. Reaching that line means every candidate was discarded.

The solution in C#

class Solution {
    public int Find(int[] nums, int value) {
        int left = 0, right = nums.Length - 1;
        while (left <= right) {
            int 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;
    }
}

C# details

Why left + (right - left) / 2. The expression (left + right) / 2 gives the same index, but the sum left + right can exceed int.MaxValue for huge arrays. C# does not warn about this: by default an int overflow wraps around silently to a negative number, and the index would then be invalid. Subtracting first keeps every intermediate value in range.
Declaring two variables at once. int left = 0, right = nums.Length - 1; declares two int variables of the same type in one statement.
The + 1 and - 1 matter. If you wrote left = middle when nums[middle] < value, then with left == middle the range would never shrink and the loop would run forever.
Return type. The method returns an int index, and -1 is a safe "not found" signal because no valid index is negative.

The built-in version

C# already has binary search in the library: Array.BinarySearch(nums, value) returns the index if the value is found. If it is not found, it returns a negative number, the bitwise complement (~) of the index where the value would be inserted, so you cannot compare against exactly -1. Writing it yourself, as in this lesson, is how you learn the pattern that many harder problems reuse.

Complexity

Time: O(log n). Each iteration halves the range, so the loop runs at most about log₂ n + 1 times.

Space: O(1). The method uses three integers, whatever the array size.

Edge cases and common mistakes

Empty array. right is -1, the loop condition 0 <= -1 is false, and the method returns -1.
Value at either end. Find([1, 2, 4, 5], 1) returns 0 and Find([1, 2, 4, 5], 5) returns 3.
Value missing. Find([1, 2, 4, 5], 3) returns -1.
Using < in the loop. The last remaining element is skipped, and searches for it fail.
Unsorted input. Binary search relies on the order. On an unsorted array it can miss values that are present.
Duplicates. With repeated values, the method returns the index of some match, not necessarily the first or last one. Finding a boundary needs a different variant, such as the lower bound.

Key takeaways

Binary search needs a sorted array and runs in O(log n), against O(n) for a linear search.
Keep an inclusive range [left, right] and loop while it is non-empty.
Move past middle with middle + 1 or middle - 1, never to middle itself.
Compute the midpoint as left + (right - left) / 2 to avoid overflow.

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