Scribd
Upload
17 views2 pages

Search Insert Position Assignment CPP

The document presents a C++ solution for finding the search insert position of a target value in a sorted array of distinct integers. It describes an algorithm that runs in O(log n) time complexity using binary search. Example inputs and outputs are provided to illustrate the functionality of the solution.

Uploaded by

akashgadde05
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
17 views2 pages

Search Insert Position Assignment CPP

The document presents a C++ solution for finding the search insert position of a target value in a sorted array of distinct integers. It describes an algorithm that runs in O(log n) time complexity using binary search. Example inputs and outputs are provided to illustrate the functionality of the solution.

Uploaded by

akashgadde05
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Assignment Solution: Search Insert Position (C++)

Problem Statement:
Given a sorted array of distinct integers and a target value, return the index if the target is found. If
not, return the index where it would be if it were inserted in order.

Note: The algorithm must run in O(log n) time complexity.

#include <vector>
using namespace std;

int searchInsert(vector<int>& nums, int target) {


int left = 0, right = [Link]() - 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;
}

// If not found, left will be the correct insert position


return left;
}

Example Usage:

Input: nums = [1, 3, 5, 6], target = 5


Output: 2

Input: nums = [1, 3, 5, 6], target = 2


Output: 1

Explanation:
- If target is found, return its index.
- If not found, return the index where it can be inserted in sorted order.

You might also like