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.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5int searchInsert(vector<int>& nums, int target) {
6 int left = 0, right = nums.size() - 1;
7 while (left <= right) {
8 int mid = left + (right - left) / 2;
9 if (nums[mid] == target) return mid;
10 else if (nums[mid] < target) left = mid + 1;
11 else right = mid - 1;
12 }
13 return left;
14}
15
16int main() {
17 vector<int> nums = {1, 3, 5, 6};
18 int target = 5;
19 cout << searchInsert(nums, target) << endl;
20 return 0;
21}
22The C++ solution performs a binary search to determine the target's index or its insertion point.
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.
1using System;
public class Program
{
public static int RecursiveBinarySearch(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 RecursiveBinarySearch(nums, mid + 1, right, target);
else
return RecursiveBinarySearch(nums, left, mid - 1, target);
}
public static int SearchInsert(int[] nums, int target)
{
return RecursiveBinarySearch(nums, 0, nums.Length - 1, target);
}
public static void Main()
{
int[] nums = {1, 3, 5, 6};
Console.WriteLine(SearchInsert(nums, 5));
}
}
This C# code uses recursion inside the binary search to find where the target is or should be inserted.