Search Insert Position leetcode solution in cpp

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

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

        return left;
    }
};

This is the solution for the "Search Insert Position" problem on LeetCode, implemented in C++.

The problem is to find the index at which the target value should be inserted into a sorted array. If the target is already present in the array, the function should return its index. If not, it should return the index where it would be inserted while maintaining the sorted order of the array.

The function searchInsert takes two parameters: nums, which is the sorted array, and target, which is the value to be inserted.

The function initializes two pointers, left and right, to the start and end of the array, respectively. The left pointer represents the lower bound of the range being searched, and the right pointer represents the upper bound.

The function then enters a while loop that continues until the left pointer is greater than the right pointer. This means that the search range has been narrowed down to a single element or is empty.

Inside the loop, the function calculates the middle index of the current search range using the formula mid = left + (right - left) / 2. This ensures that mid is always rounded down to the nearest integer.

The function then checks if the value at the middle index, nums[mid], is equal to the target value. If it is, the function returns mid as the index of the target value in the array.

If nums[mid] is less than the target value, it means that the target value should be inserted to the right of mid. In this case, the left pointer is updated to mid + 1.

If nums[mid] is greater than the target value, it means that the target value should be inserted to the left of mid. In this case, the right pointer is updated to mid - 1.

After the while loop, if the target value is not found in the array, the left pointer represents the index where the target value should be inserted to maintain the sorted order. The function returns left as the result.

This solution has a time complexity of O(log n), where n is the size of the input array. The binary search algorithm is used to efficiently find the target value or the insertion position.