Start learning free

LESSON 248 OF 347 · BINARY SEARCH

Lower Bound in C#: Binary Search for the Insertion Index

Practice O(log n) Read the full explanation

Given a sorted array of integers nums, find the smallest index where we can place a given value such that the array remains sorted

Example 1:

Input: nums = [1, 2, 3, 5, 7], value = 4
Output: 3
Explanation: Placing the value 4 on the 4th index we obtain nums = [1, 2, 3, 4, 5, 7]

Example 2:

Input: nums = [1, 2, 3], value = 2
Output: 1
Explanation: Placing the value 2 on the 1st index we obtain nums = [1, 2, 2, 3]

Note:

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


STEP 1 OF 6
    Ctrl + Enter to check

    C# · BINARY SEARCH

    Lower Bound in C#, explained

    Problem overview

    The method LowerBound receives a sorted int[] nums and an int value. It returns the smallest index at which value could be inserted so that the array stays sorted. Equivalently, it returns the index of the first element that is not less than value.

    For nums = [1, 2, 3, 5, 7] and value = 4, inserting 4 at index 3 gives [1, 2, 3, 4, 5, 7], so the answer is 3. For nums = [1, 2, 3] and value = 2, the 2 can go in front of the existing 2, at index 1, so the answer is 1. When the value is already present, the result is the index of its first occurrence.

    The statement asks for O(log n) time and O(1) extra space, which points to binary search.

    Approach: binary search for the first element that is not smaller

    Think of each element as answering one question: "is nums[i] < value?" Because the array is sorted, the answers form a block of true values followed by a block of false values. The lower bound is the index where the answers switch from true to false. If every answer is true, the switch point is nums.Length, one past the last index, which is exactly where the value belongs.

    Binary search finds a switch point like this. Look at the middle element. If it is smaller than value, then it and everything to its left are in the true block, so the answer lies to the right. Otherwise the middle element is at least value, so it could be the answer or the answer is further left, and everything to the right can be ignored.

    Unlike the plain binary search for an exact match, there is no early return. The loop always runs until the range is empty, because even after seeing a matching value there might be an earlier copy of it.

    Step by step

    1. Set the bounds. left = 0 and right = nums.Length - 1, both inclusive, so the window covers the whole array.
    2. Loop while left <= right. The window may shrink to a single element before it becomes empty.
    3. Compute middle as (left + right) / 2. Integer division rounds down, so middle is always a valid index in the window.
    4. If nums[middle] < value, move left to middle + 1. Everything up to middle is too small to be the answer.
    5. Otherwise move right to middle - 1. The element at middle is at least value, so the answer is at middle or earlier. Moving right to middle - 1 keeps searching to the left. If middle itself was the answer, no earlier index will turn out to be valid, so left stays where it is and ends up pointing at it.
    6. Return left. After the loop it points at the first index whose element is at least value.

    Why left is the answer: during the loop, every index before left holds a value smaller than value, and every index after right holds a value that is at least value. When the loop ends, right equals left - 1, so the two facts meet: everything before left is too small and everything from left onward is not.

    The solution in C#

    class Solution {
    public int LowerBound(int[] nums, int value) {
        int left = 0, right = nums.Length- 1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] < value) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return left;
    }
}

    Tracing [1, 2, 3, 5, 7] with value = 4: the window is 0 to 4, middle is 2 and nums[2] = 3 is less than 4, so left becomes 3. The window 3 to 4 has middle = 3 and nums[3] = 5 is not less than 4, so right becomes 2. Now left > right, and the method returns 3.

    C# details:

    • Midpoint arithmetic. (left + right) / 2 is fine for arrays of ordinary size. For an array longer than about a billion elements, left + right could exceed int.MaxValue and wrap around to a negative number without any error. left + (right - left) / 2 avoids that and gives the same index otherwise.
    • Integer division. Dividing two int values in C# discards the fraction, so no Math.Floor is needed.
    • Comparing with <. The test nums[middle] < value on two int values compares the numbers directly.
    • Library equivalent. Array.BinarySearch finds a match but, when there are duplicates, does not promise which one. It is not a lower bound.

    Complexity

    Time: O(log n). Every iteration cuts the window roughly in half, so the loop runs at most about log₂ n + 1 times.

    Space: O(1). Only left, right and middle are stored.

    Edge cases and common mistakes

    • Value larger than everything. [1, 2, 3] with value 9 returns 3, which is nums.Length. This index is a valid insertion position even though it is not a valid element index, so do not use it to read the array.
    • Value smaller than everything. [1, 2, 3] with value -5 returns 0.
    • Empty array. right is -1, the loop does not run, and the method returns 0, the only place to insert into an empty array.
    • Duplicates. [1, 2, 2, 2, 3] with value 2 returns 1, the first 2. Returning early on a match, as in the exact-match binary search, would return whichever 2 the search landed on.
    • Returning right. After the loop right is one less than the answer. Return left.
    • Using <= in the comparison. With nums[middle] <= value, the method returns the first element greater than the value, the upper bound, which differs when the value is present.

    Testing

    • [1, 2, 3, 5, 7], value 4 gives 3.
    • [1, 2, 3], value 2 gives 1.
    • [1, 2, 3], value 9 gives 3, and value -5 gives 0.
    • [], value 1 gives 0.
    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