Trusted answers to developer questions

Harsh Jain

In this shot, we'll discuss binary search*.* The problem statement is given below:

We are given a sorted array of distinct integers `nums`

and a `target`

value. Our task is to find out the index if the `target`

is found. If not, we need to return the index where the `target`

would be inserted. Remember, if the `target`

is not found, the index at which the `target`

could be placed should still keep the array `nums`

as sorted.

For example, let's assume that the given array is `[1, 2, 4, 5, 6, 7]`

,** **and the target value is `3`

. The solution for this input will be `2`

. Since the target could be inserted at index `2`

** **to keep the array sorted.

Let's now discuss the approach to solve this problem. We can take some time to think about the solution to this problem and then proceed further.

We'll follow the steps mentioned below to solve the given problem:

- We'll first apply the binary search algorithm on the given sorted array.
- If the target value is found, we'll return that index.
- If not, we'll process until our search space becomes empty. At this point, the index at which the element should be inserted is already saved while we dive our search space by half.

#include <iostream> #include <vector> using namespace std; int searchInsert(vector<int>& nums, int target) { int start = 0; int end = nums.size() - 1; while(start <= end){ int mid = start + (end - start)/2; if (nums[mid] == target) return mid; else if (nums[mid] < target) start = mid + 1; else end = mid - 1; } return start; } int main() { vector<int> vec = {1, 2, 4, 5, 6, 7}; int target = 3; int index = searchInsert(vec, target); cout << "Index: " << index; return 0; }

Solution to the Search Insert Position problem

- Lines 5–21: We create a function
`searchInsert()`

. This function will accept a vector of sorted integers and the target value. Next, it will apply the binary search algorithm - Lines 12 and 13: If the
`target`

is found, we return that index. If the`target`

is not found, we continue executing the loop until our start index becomes greater than the end index. In the end, the value in the`start`

variable will actually contain the index at which that element could be inserted, and the array will remain sorted after the insertion. - Lines 27 and 28: We call the function and print the index for the provided
`target`

.

Note:To learn and solve more coding interview questions, refer to this course: Competitive Programming - Crack Your Coding Interview, C++.

RELATED TAGS

c++

communitycreator

CONTRIBUTOR

Harsh Jain

RELATED COURSES

View all Courses

Keep Exploring

Related Courses