Sponsored
Sponsored
The iterative binary search approach involves using two pointers, 'left' and 'right'. We continue dividing the array into halves until we locate the target or determine where it should be inserted. The algorithm compares the target with the middle element and appropriately adjusts the 'left' or 'right' pointer based on this comparison.
Time Complexity: O(log n)
Space Complexity: O(1) since no extra space is used.
1def searchInsert(nums, target):
2 left, right = 0, len(nums) - 1
3 while left <= right:
4 mid = left + (right - left) // 2
5 if nums[mid] == target:
6 return mid
7 elif nums[mid] < target:
8 left = mid + 1
9 else:
10 right = mid - 1
11 return left
12
13nums = [1, 3, 5, 6]
14target = 5
15print(searchInsert(nums, target))
16The Python solution efficiently finds the index or insert position of the target using binary search technique.
In this approach, the binary search is implemented recursively. The function calls itself with updated bounds until the target is found or until it determines the correct insertion index. This approach makes use of stack space due to recursion but is logically intuitive.
Time Complexity: O(log n)
Space Complexity: O(log n) due to recursion stack.
1#include <iostream>
#include <vector>
using namespace std;
int binarySearch(vector<int>& nums, int left, int right, int target) {
if (left > right) return left;
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target)
return binarySearch(nums, mid+1, right, target);
else
return binarySearch(nums, left, mid-1, target);
}
int searchInsert(vector<int>& nums, int target) {
return binarySearch(nums, 0, nums.size() - 1, target);
}
int main() {
vector<int> nums = {1, 3, 5, 6};
int target = 5;
cout << searchInsert(nums, target) << endl;
return 0;
}
The C++ version implements a recursive form of binary search to decide on the position of the target.