Start learning free

LESSON 269 OF 410 · BINARY SEARCH

Lower Bound in O(log n) Time Complexity using Java

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 at index 3 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 at index 1 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

    JAVA · BINARY SEARCH

    Lower Bound in Java, explained

    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" or "insertion point".

    Common applications include binary search trees, databases, and any system that requires maintaining a sorted list of elements.

    Potential pitfalls include misunderstanding the requirement to maintain the sorted order and not considering edge cases such as inserting at the beginning or end of the array.

    Approach

    To solve this problem efficiently, we can use a binary search algorithm. A naive approach would involve iterating through the array and finding the correct position, which would take O(n) time. However, since the array is sorted, we can leverage binary search to achieve O(log n) time complexity.

    Naive Solution

    The naive solution involves iterating through the array and finding the first position where the value is greater than or equal to the given value. This approach is not optimal as it has a time complexity of O(n).

    Optimized Solution

    The optimized solution uses binary search to find the correct insertion point. Binary search works by repeatedly dividing 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 given value, move the left pointer to mid + 1.
      • Otherwise, move the right pointer to mid - 1.
    3. Return the left pointer as the insertion point.

    Code Implementation

    public class LowerBound {
    public static int findInsertionIndex(int[] nums, int value) {
        int left = 0;
        int right = nums.length - 1;

        // Binary search for the insertion point
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < value) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 5, 7};
        int value1 = 4;
        System.out.println(findInsertionIndex(nums1, value1)); // Output: 3

        int[] nums2 = {1, 2, 3};
        int value2 = 2;
        System.out.println(findInsertionIndex(nums2, value2)); // Output: 1
    }
}

    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 not using any additional space that scales with the input size.

    Edge Cases

    Potential edge cases include:

    • Inserting at the beginning of the array (e.g., nums = [2, 3, 4], value = 1).
    • Inserting at the end of the array (e.g., nums = [1, 2, 3], value = 4).
    • Inserting a value that already exists in the array (e.g., nums = [1, 2, 3], value = 2).

    Each of these cases is handled correctly by the binary search algorithm.

    Testing

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

    • Simple cases with small arrays.
    • Edge cases with values at the beginning or end of the array.
    • Cases with duplicate values in the array.

    Using a testing framework like JUnit can help automate and validate these test cases.

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Understand the problem requirements and constraints thoroughly.
    • Think about the properties of the input data (e.g., sorted array) and how they can be leveraged.
    • Start with a simple, naive solution and then optimize it.
    • Practice similar problems to improve problem-solving skills.

    Conclusion

    In this blog post, we discussed how to find the correct insertion point 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

    For further reading and practice, consider the following resources:

    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free