Department of CSE LeetCode Practice Report
Problem 1: Search Insert Position
a) Problem Statement
Given a sorted array of distinct integers and a target value, the task is to determine the
index at which the target appears in the array. If the target is not present, the function
must return the index where it would be inserted so that the array remains sorted.
The solution must run in O(log n) time complexity, meaning a linear scan through the
array is not acceptable. The input array is guaranteed to have no duplicate elements
and is sorted in ascending order.
Constraints:
• 1 ≤ [Link] ≤ 10⁴
• −10⁴ ≤ nums[i] ≤ 10⁴
• nums contains distinct values sorted in ascending order.
• −10⁴ ≤ target ≤ 10⁴
Example 1:
Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Reason: Target 5 is present at index 2.
Example 2:
Input: nums = [1, 3, 5, 6], target = 2
Output: 1
Reason: Target 2 is not found. It would fit between index 0 and 1, so the answer is 1.
Example 3:
Input: nums = [1, 3, 5, 6], target = 7
Output: 4
Reason: Target 7 is greater than all elements, so it would be appended at the end.
<Name of Student> | <USN> | Course: Analysis and Design of Algorithms
Department of CSE LeetCode Practice Report
b) Algorithm
1. Accept the sorted array nums and the integer target as
inputs.
2. Set two pointers: low = 0 and high = [Link]() - 1.
3. Begin a loop that continues as long as low <= high:
3a. Calculate mid = (low + high) / 2.
3b. If nums[mid] >= target, the current mid is a candidate
answer.
. Move high = mid - 1 to search for a potentially
smaller valid index.
3c. If nums[mid] < target, the target must lie to the right.
. Move low = mid + 1.
4. When the loop ends, low holds the leftmost position where
target exists or should be inserted.
5. Return low.
Time Complexity: O(log n) — search space halves each iteration.
Space Complexity: O(1) — no extra data structures used.
c) Code Implementation
class Solution {
public:
int searchInsert(vector<int> &nums, int target) {
int low = 0;
int high = [Link]() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] >= target) {
// mid is a potential answer; look left for smaller
index
high = mid - 1;
}
else {
// target is larger; eliminate left half
low = mid + 1;
}
}
// low is the first position where nums[low] >= target
return low;
}
};
<Name of Student> | <USN> | Course: Analysis and Design of Algorithms
Department of CSE LeetCode Practice Report
d) Test Cases Considered
Test Case Input Expected Output Actual Output Result
TC 1 nums=[1,3,5,6], 2 2 PASS
target=5
TC 2 nums=[1,3,5,6], 1 1 PASS
target=2
TC 3 nums=[1,3,5,6], 4 4 PASS
target=7
All three test cases pass. The solution correctly handles the case where the target is
present, where it must be inserted in the middle, and where it falls beyond all existing
elements.
<Name of Student> | <USN> | Course: Analysis and Design of Algorithms