Sponsored
Sponsored
The iterative binary search approach involves using a loop to divide the array into halves repeatedly until the target is found or the search range is empty. This approach utilizes two pointers, 'low' and 'high', that represent the current search bounds.
Time Complexity: O(log n), as we divide the search space in half each time.
Space Complexity: O(1), only a constant amount of space is used.
1using System;
2
3public class Solution {
4 public int Search(int[] nums, int target) {
5 int low = 0, high = nums.Length - 1;
6 while (low <= high) {
7 int mid = low + (high - low) / 2;
8 if (nums[mid] == target) return mid;
9 else if (nums[mid] < target) low = mid + 1;
10 else high = mid - 1;
11 }
12 return -1;
13 }
14
15 public static void Main(string[] args) {
16 Solution sol = new Solution();
17 int[] nums = {-1, 0, 3, 5, 9, 12};
18 int target = 9;
19 Console.WriteLine(sol.Search(nums, target));
20 }
21}The C# solution uses a while loop to adjust the search space by modifying the 'low' and 'high' pointers based on comparisons.
The recursive binary search involves calling a function that repeatedly calls itself with updated bounds until the target is found or the bounds overlap. This approach provides a cleaner implementation at the cost of additional space used by the call stack.
Time Complexity: O(log n)
Space Complexity: O(log n) due to the stack space used by recursion.
1using System;
2
public class Solution {
public int BinarySearchRec(int[] nums, int low, int high, int target) {
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) return BinarySearchRec(nums, mid + 1, high, target);
return BinarySearchRec(nums, low, mid - 1, target);
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {-1, 0, 3, 5, 9, 12};
int target = 9;
Console.WriteLine(sol.BinarySearchRec(nums, 0, nums.Length - 1, target));
}
}This C# solution for binary search uses recursive calls to adjust the search space, eventually finding the target or deducing its absence.