Algocademy Logo

Lower Bound in O(log n) Time Complexity using C++


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.


Understanding the Problem

The core challenge of this problem is to find the correct position to insert a given value into a sorted array such that the array remains sorted. This is a common problem in computer science, often referred to as finding the "lower bound" of a value in a sorted array.

Common applications include binary search algorithms, insertion operations in sorted data structures, and more.

Potential pitfalls include misunderstanding the requirement to maintain the sorted order and not optimizing the search process, which should be done in O(log n) time.

Approach

To solve this problem, we can use a binary search algorithm. The naive approach would be to iterate through the array and find the correct position, which would take O(n) time. However, this is not optimal.

Using binary search, we can reduce the time complexity to O(log n). The idea is to repeatedly divide the search interval in half. If the value is less than the middle element, we search the left half; otherwise, we search the right half.

Algorithm

Here is a step-by-step breakdown of the binary search algorithm:

  1. Initialize two pointers, left and right, to the start and end of the array, respectively.
  2. While left is less than or equal to right:
    • Calculate the middle index mid.
    • If nums[mid] is less than the value, move the left pointer to mid + 1.
    • Otherwise, move the right pointer to mid - 1.
  3. Return the left pointer as the insertion index.

Code Implementation

#include <vector>
#include <iostream>

int lowerBound(const std::vector<int>& nums, int value) {
    int left = 0;
    int right = nums.size() - 1;
    
    // Binary search for the lower bound
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] < value) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return left;
}

int main() {
    std::vector<int> nums1 = {1, 2, 3, 5, 7};
    int value1 = 4;
    std::cout << "Index to insert " << value1 << " in nums1: " << lowerBound(nums1, value1) << std::endl;
    
    std::vector<int> nums2 = {1, 2, 3};
    int value2 = 2;
    std::cout << "Index to insert " << value2 << " in nums2: " << lowerBound(nums2, value2) << std::endl;
    
    return 0;
}

Complexity Analysis

The time complexity of the binary search algorithm is O(log n) because we are dividing the search interval in half at each step. The space complexity is O(1) as we are using only a constant amount of extra space.

Edge Cases

Potential edge cases include:

Each of these cases is handled by the binary search algorithm, as it correctly identifies the position to maintain the sorted order.

Testing

To test the solution comprehensively, consider the following test cases:

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to understand the requirements and constraints. Binary search is a powerful technique for problems involving sorted arrays. Practice similar problems to develop a strong understanding of binary search and its applications.

Conclusion

In this blog post, we discussed how to find the lower bound of a value in a sorted array using binary search. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing efficient algorithms and improving problem-solving skills.

Additional Resources