Search insert position of K in a sorted array

JavaView on GFG

Intuition

Find index to insert k in sorted array (or return existing index). Binary search lower_bound.

Algorithm

1Binary search: find first position where arr[pos] >= k.

Common Pitfalls

•Same as LC 35. Binary search lower bound. O(log n).

Search insert position of K in a sorted array.java

Java

// Approach: Binary search. Return mid if found, or the position where K would be inserted.
// Time: O(log n) Space: O(1)
class Solution {
    public int searchInsertK(int arr[], int k) {
        int low = 0, high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == k)
                return mid;
            else if (arr[mid] < k)
                low = mid + 1;
            else
                high = mid - 1;
        }
        
        return low; // insert position
    }
};

Was this solution helpful?