Scribd
Upload
15 views5 pages

ADA Assignment

The document presents an assignment on the 'Search Insert Position' problem, detailing the use of a binary search algorithm on a sorted list to find the appropriate insertion index for a target value. It outlines the time complexity as O(log n) and space complexity as O(1), highlighting the efficiency of the binary search approach compared to a linear search alternative. Additionally, it includes pseudocode and a Python implementation demonstrating the algorithm's functionality.

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
15 views5 pages

ADA Assignment

The document presents an assignment on the 'Search Insert Position' problem, detailing the use of a binary search algorithm on a sorted list to find the appropriate insertion index for a target value. It outlines the time complexity as O(log n) and space complexity as O(1), highlighting the efficiency of the binary search approach compared to a linear search alternative. Additionally, it includes pseudocode and a Python implementation demonstrating the algorithm's functionality.

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
You are on page 1/ 5

Department of Computer Science (DATA SCIENCE)

ASSIGNMENT ON

“Search Insert Position”


COURSE CODE: BCS405A SEMESTER: 4TH

Submitted by
AKASH (3GN23CD006)

Under The Guidance Of:


Assistant Prof. Syed Saqlain Ahmed
➢ Data Structure Being Employed
The primary data structure used is a list (array). The list is
assumed to be sorted in ascending order as per the
problem constraints.

AlgorithmApproach (Pseudocode)-

function searchInsertPosition(nums, target):


left ← 0
right ← length(nums) - 1

while left ≤ right:


mid ← (left + right) // 2

if nums[mid] == target:
return mid
else if nums[mid] < target:
left ← mid + 1
else:
right ← mid - 1

return left
➢ Planting Upper and Lower Bound:-
Best Case (Lower Bound): O(1), when the target is found at the
first middle check. Worst Case (Upper Bound): O(log n), when the
target is not found and binary search traverses the entire log n
depth

➢ Time Complexity:-
• Binary Search works by repeatedly dividing the array into
two halves. In each step:
• You eliminate half of the remaining elements from consideration.
• The number of steps required is proportional to the logarithm of
the number of elements in the array.
Let n be the length of the list.
• At each iteration, we do:
o One comparison
o One midpoint calculation
• Number of iterations ≈ log₂(n)
◆ Time Complexity= O(logn)

➢ Space Complexity:-
We are not using any additional data structures, and the algorithm only uses a fixed
number of variables (left, right, mid, etc.).

• No recursion is involved (as this is an iterative binary search).


• No extra space that grows with input size is used.

◆ Space Complexity= 0(1)


➢ Alternative Solution:

By Linear Search Approach

• Start from the beginning of the array.


• Traverse each element and check:
If nums[i] >= target, then insert at position i.

◆ Pseudocode-

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


int left = 0;
int right = nums.size() - 1;

while (left <= right) {


int mid = (left + right) / 2;

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

return left;
}
➢ Running code-
def searchInsert(nums, target):
left, right = 0, len(nums) - 1

while left <= right:


mid = (left + right) // 2

if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1

return left

# Example usage
nums = [1, 3, 5, 6]
target = 5
print("Insert Position:", searchInsert(nums, target)) # Output: 2

target = 2
print("Insert Position:", searchInsert(nums, target)) # Output: 1

target = 7
print("Insert Position:", searchInsert(nums, target)) # Output: 4

You might also like