Master the most fundamental algorithms for finding elements. From linear search to advanced binary search variations, binary search on answer, and specialized techniques—comprehensive coverage with 45+ C# code examples and 11 complete LeetCode problem solutions.
Linear search is the simplest search algorithm: examine elements one by one until you find the target or reach the end. It's the baseline for understanding search efficiency and serves as the foundation for grasping why binary search is so powerful.
Linear search works on any array, sorted or unsorted. You start at one end and check each element sequentially. While slow for large datasets, it's often the right choice for small arrays or when data isn't sorted.
public static int LinearSearch(int[] arr, int target) { for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) return i; } return -1; }
Explanation: We iterate through each element. Best case: target is at index 0 (one comparison). Worst case: target is at the end or doesn't exist (n comparisons). Average case: target found at position n/2 (n/2 comparisons), still O(n).
A clever optimization: place a copy of the target at the end of the array (a "sentinel"). This eliminates the need to check array bounds on each iteration—the loop always terminates when it finds the sentinel.
public static int SentinelLinearSearch(int[] arr, int target) { int last = arr[arr.Length - 1]; arr[arr.Length - 1] = target; // Place sentinel int i = 0; while (arr[i] != target) i++; arr[arr.Length - 1] = last; // Restore original value // If we found sentinel at position length-1, target wasn't in array if (i == arr.Length - 1 && last != target) return -1; return i; }
This approach reduces memory traffic (fewer comparisons with array bounds) and can be 10-20% faster in practice, though the asymptotic complexity remains O(n).
Binary search is a masterclass in algorithmic thinking. By eliminating half the search space each iteration, it reduces O(n) to O(log n)—a stunning improvement. For 1 million items, binary search needs at most 20 comparisons.
Binary search requires a sorted array. The algorithm works by maintaining two pointers (left and right) and repeatedly checking the middle element:
Let's search for target = 7 in array: [1, 3, 5, 7, 9, 11, 13]
Array: [1, 3, 5, 7, 9, 11, 13] Target: 7 Iteration 1: left=0, right=6, mid=3 arr[3]=7 equals target Found at index 3! Return 3
Another example with target = 6 (not in array):
Array: [1, 3, 5, 7, 9, 11, 13] Target: 6 Iteration 1: left=0, right=6, mid=3 arr[3]=7 > target, so right=2 Iteration 2: left=0, right=2, mid=1 arr[1]=3 < target, so left=2 Iteration 3: left=2, right=2, mid=2 arr[2]=5 < target, so left=3 left > right: Exit loop, return -1
public static int BinarySearch(int[] arr, int target) { int left = 0; int right = arr.Length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }
public static int BinarySearchRecursive(int[] arr, int target, int left, int right) { if (left > right) return -1; int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) return BinarySearchRecursive(arr, target, mid + 1, right); return BinarySearchRecursive(arr, target, left, mid - 1); } // Call: BinarySearchRecursive(arr, target, 0, arr.Length - 1)
This is a classic gotcha that trips up even experienced developers. Consider calculating the midpoint:
Standard binary search finds any occurrence of the target. Often, you need specific variations: find the leftmost position, find the rightmost, or find an insertion point. These variations build on the core algorithm with subtle but critical changes.
When the array has duplicates, find the index of the first (leftmost) occurrence of the target.
public static int FindFirstOccurrence(int[] arr, int target) { int left = 0; int right = arr.Length - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { result = mid; right = mid - 1; // Continue searching left half for earlier occurrence } else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return result; }
Key difference: When we find a match, we don't return immediately. Instead, we save it and continue searching the left half to find an earlier occurrence.
Find the index of the last (rightmost) occurrence of the target.
public static int FindLastOccurrence(int[] arr, int target) { int left = 0; int right = arr.Length - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { result = mid; left = mid + 1; // Continue searching right half for later occurrence } else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return result; }
Find the position where the target should be inserted to keep the array sorted. If the target exists, lower bound returns where it begins; upper bound returns where it ends.
// Lower bound: smallest index where arr[i] >= target public static int LowerBound(int[] arr, int target) { int left = 0; int right = arr.Length; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < target) left = mid + 1; else right = mid; } return left; } // Upper bound: smallest index where arr[i] > target public static int UpperBound(int[] arr, int target) { int left = 0; int right = arr.Length; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] <= target) left = mid + 1; else right = mid; } return left; }
C# provides built-in binary search methods. These return the index if found, or a negative number indicating where to insert if not found.
int[] arr = new int[] { 1, 3, 5, 7, 9 }; // Array.BinarySearch int index = Array.BinarySearch(arr, 5); // index = 2 (found at position 2) index = Array.BinarySearch(arr, 6); // index = -4 (not found; would insert at ~-4 = 3) // List.BinarySearch List<int> list = new List<int> { 1, 3, 5, 7, 9 }; index = list.BinarySearch(5); // index = 2 (found)
An array is rotated when a portion at the end is moved to the front. Example: [4, 5, 6, 7, 0, 1, 2] is [0, 1, 2, 4, 5, 6, 7] rotated. The trick: one half is always sorted.
public static int SearchRotatedArray(int[] arr, int target) { int left = 0; int right = arr.Length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; // Determine which half is sorted if (arr[left] <= arr[mid]) { // Left half is sorted if (arr[left] <= target && target < arr[mid]) right = mid - 1; else left = mid + 1; } else { // Right half is sorted if (arr[mid] < target && target <= arr[right]) left = mid + 1; else right = mid - 1; } } return -1; }
In a rotated sorted array, the minimum is the "rotation point." Use binary search to find it in O(log n).
public static int FindMin(int[] arr) { int left = 0; int right = arr.Length - 1; while (left < right) { int mid = left + (right - left) / 2; // If mid is greater than right, minimum is in the right part if (arr[mid] > arr[right]) left = mid + 1; else right = mid; } return arr[left]; }
A matrix where each row is sorted left-to-right and the first element of each row is greater than the last element of the previous row. Treat it as a flattened 1D sorted array.
public static bool SearchMatrix(int[][] matrix, int target) { int rows = matrix.Length; int cols = matrix[0].Length; int left = 0; int right = rows * cols - 1; while (left <= right) { int mid = left + (right - left) / 2; int row = mid / cols; int col = mid % cols; int midValue = matrix[row][col]; if (midValue == target) return true; if (midValue < target) left = mid + 1; else right = mid - 1; } return false; }
A peak is an element greater than its neighbors. Find any peak in O(log n) time (not necessarily the maximum).
public static int FindPeak(int[] arr) { int left = 0; int right = arr.Length - 1; while (left < right) { int mid = left + (right - left) / 2; // If mid is less than its right neighbor, peak is to the right if (arr[mid] < arr[mid + 1]) left = mid + 1; else right = mid; } return left; }
This is a paradigm shift: instead of searching for an element in an array, we binary search on the solution space itself. The key insight is recognizing when a feasible answer exists, then searching for the optimal one.
Template: "Can we achieve X? If yes, try a smaller X. If no, try a larger X." This requires:
Problem: Koko has n piles of bananas. She wants to finish eating all bananas in h hours. She can choose an eating speed k (bananas per hour). In each hour, she eats k bananas from one pile; if a pile has fewer than k bananas, she eats them all in one hour and waits. Find the minimum speed k such that she finishes in h hours.
public static int MinEatingSpeed(int[] piles, int h) { int left = 1; int right = piles.Max(); while (left < right) { int mid = left + (right - left) / 2; if (CanFinish(piles, h, mid)) right = mid; // Try slower speeds else left = mid + 1; // Need faster speed } return left; } private static bool CanFinish(int[] piles, int h, int speed) { long hoursNeeded = 0; foreach (int pile in piles) { hoursNeeded += (pile + speed - 1) / speed; // Ceiling division } return hoursNeeded <= h; }
How it works: Search space is [1, max_pile]. For any speed, we can calculate hours needed. If feasible, try a slower speed. If infeasible, try faster. Time: O(n log max_pile).
Problem: Split an array into m subarrays such that the maximum sum of any subarray is minimized. Find this minimized maximum sum.
public static int SplitArray(int[] nums, int m) { int left = nums.Max(); int right = nums.Sum(); while (left < right) { int mid = left + (right - left) / 2; if (CanSplit(nums, m, mid)) right = mid; else left = mid + 1; } return left; } private static bool CanSplit(int[] nums, int m, int maxSum) { int splits = 1; long currentSum = 0; foreach (int num in nums) { if (currentSum + num <= maxSum) currentSum += num; else { splits++; currentSum = num; if (splits > m) return false; } } return true; }
Problem: Ship packages over d days. Each day, load packages with max weight of capacity c in order (can't skip). Find minimum capacity.
public static int ShipWithinDays(int[] weights, int days) { int left = weights.Max(); int right = weights.Sum(); while (left < right) { int mid = left + (right - left) / 2; if (CanShip(weights, days, mid)) right = mid; else left = mid + 1; } return left; } private static bool CanShip(int[] weights, int days, int capacity) { int daysUsed = 1; long currentLoad = 0; foreach (int w in weights) { if (currentLoad + w <= capacity) currentLoad += w; else { daysUsed++; currentLoad = w; if (daysUsed > days) return false; } } return true; }
Ternary search works on unimodal functions (functions with a single peak or valley). Instead of dividing by 2, divide by 3. Time complexity: O(log₃ n) ≈ O(log n), slightly worse than binary search theoretically, but sometimes better in practice for specific patterns.
// Find maximum in a unimodal array public static int TernarySearchMax(int[] arr) { int left = 0; int right = arr.Length - 1; while (right - left > 2) { int mid1 = left + (right - left) / 3; int mid2 = right - (right - left) / 3; if (arr[mid1] > arr[mid2]) right = mid2 - 1; else left = mid1 + 1; } int maxVal = arr[left]; for (int i = left + 1; i <= right; i++) maxVal = Math.Max(maxVal, arr[i]); return maxVal; }
For uniformly distributed data, interpolation search can beat binary search. Instead of guessing the midpoint, estimate where the target is based on its value distribution.
public static int InterpolationSearch(int[] arr, int target) { int left = 0; int right = arr.Length - 1; while (left <= right && target >= arr[left] && target <= arr[right]) { // Estimate position based on value int pos = left + (int)((double)(right - left) / (arr[right] - arr[left]) * (target - arr[left])); if (arr[pos] == target) return pos; if (arr[pos] < target) left = pos + 1; else right = pos - 1; } return -1; }
Average Time: O(log log n) for uniformly distributed data. Worst Case: O(n) if data is skewed. Rarely used in practice; binary search is safer and almost always faster.
Useful for unbounded or infinite arrays. First, find a range [2^k, 2^(k+1)) containing the target via exponential jumps. Then binary search within that range.
public static int ExponentialSearch(int[] arr, int target) { if (arr[0] == target) return 0; // Find range [2^i, 2^(i+1)) int i = 1; while (i < arr.Length && arr[i] < target) i *= 2; // Binary search in range int left = i / 2; int right = Math.Min(i, arr.Length - 1); while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }
Time: O(log n). Use when: Array size is unknown, or you're searching an infinite stream.
Jump Search divides the array into blocks of size sqrt(n). Jump through blocks, then linear search within the found block. Time: O(sqrt(n)).
public static int JumpSearch(int[] arr, int target) { int n = arr.Length; int step = (int)Math.Sqrt(n); int prev = 0; // Jump through blocks while (arr[Math.Min(step, n) - 1] < target) { prev = step; step += (int)Math.Sqrt(n); if (prev >= n) return -1; } // Linear search in block [prev, step) while (arr[prev] < target) { prev++; if (prev == Math.Min(step, n)) return -1; } if (arr[prev] == target) return prev; return -1; }
Statement: Given a sorted array and target, return the index if found, else -1.
public class Solution { public int Search(int[] nums, int target) { int left = 0, right = nums.Length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } } // Time: O(log n), Space: O(1)
Statement: Given an API isBadVersion(version), find the first bad version in [1, n].
public class Solution : VersionControl { public int FirstBadVersion(int n) { int left = 1, right = n; while (left < right) { int mid = left + (right - left) / 2; if (IsBadVersion(mid)) right = mid; // First bad is at mid or before else left = mid + 1; // First bad is after mid } return left; } } // Time: O(log n), Space: O(1)
Statement: Find the index where target should be inserted to keep array sorted.
public class Solution { public int SearchInsert(int[] nums, int target) { int left = 0, right = nums.Length; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) left = mid + 1; else right = mid; } return left; } } // Time: O(log n), Space: O(1)
Statement: Find the range [first, last] of target in sorted array. Return [-1, -1] if not found.
public class Solution { public int[] SearchRange(int[] nums, int target) { int first = FindFirst(nums, target); if (first == -1) return new int[] { -1, -1 }; int last = FindLast(nums, target); return new int[] { first, last }; } private int FindFirst(int[] nums, int target) { int left = 0, right = nums.Length - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { result = mid; right = mid - 1; } else if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return result; } private int FindLast(int[] nums, int target) { int left = 0, right = nums.Length - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { result = mid; left = mid + 1; } else if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return result; } } // Time: O(log n), Space: O(1)
Statement: Search in rotated sorted array with distinct elements.
public class Solution { public int Search(int[] nums, int target) { int left = 0, right = nums.Length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; if (nums[left] <= nums[mid]) { if (nums[left] <= target && target < nums[mid]) right = mid - 1; else left = mid + 1; } else { if (nums[mid] < target && target <= nums[right]) left = mid + 1; else right = mid - 1; } } return -1; } } // Time: O(log n), Space: O(1)
public class Solution { public int FindMin(int[] nums) { int left = 0, right = nums.Length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) left = mid + 1; else right = mid; } return nums[left]; } } // Time: O(log n), Space: O(1)
public class Solution { public bool SearchMatrix(int[][] matrix, int target) { int rows = matrix.Length, cols = matrix[0].Length; int left = 0, right = rows * cols - 1; while (left <= right) { int mid = left + (right - left) / 2; int val = matrix[mid / cols][mid % cols]; if (val == target) return true; if (val < target) left = mid + 1; else right = mid - 1; } return false; } } // Time: O(log(m*n)), Space: O(1)
(See detailed solution in Section 10.4)
public class Solution { public int FindPeakElement(int[] nums) { int left = 0, right = nums.Length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < nums[mid + 1]) left = mid + 1; else right = mid; } return left; } } // Time: O(log n), Space: O(1)
Statement: Compute the integer square root of x.
public class Solution { public int MySqrt(int x) { if (x == 0) return 0; long left = 1, right = x; while (left <= right) { long mid = left + (right - left) / 2; if (mid * mid == x) return (int)mid; if (mid * mid < x) left = mid + 1; else right = mid - 1; } return (int)right; } } // Time: O(log x), Space: O(1)
Statement: Find the median of two sorted arrays. Time: O(log(min(m,n))).
public class Solution { public double FindMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.Length > nums2.Length) return FindMedianSortedArrays(nums2, nums1); int m = nums1.Length, n = nums2.Length; int left = 0, right = m; while (left <= right) { int cut1 = left + (right - left) / 2; int cut2 = (m + n + 1) / 2 - cut1; int left1 = (cut1 == 0) ? int.MinValue : nums1[cut1 - 1]; int left2 = (cut2 == 0) ? int.MinValue : nums2[cut2 - 1]; int right1 = (cut1 == m) ? int.MaxValue : nums1[cut1]; int right2 = (cut2 == n) ? int.MaxValue : nums2[cut2]; if (left1 <= right2 && left2 <= right1) { if ((m + n) % 2 == 0) return (Math.Max(left1, left2) + Math.Min(right1, right2)) / 2.0; else return Math.Max(left1, left2); } else if (left1 > right2) right = cut1 - 1; else left = cut1 + 1; } return -1.0; } } // Time: O(log(min(m,n))), Space: O(1)
Find an exact match or return -1. Used when any occurrence works.
int left = 0, right = arr.Length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1;
Find the leftmost position of target. Use when duplicates exist.
int left = 0, right = arr.Length; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < target) left = mid + 1; else right = mid; } // left is now the leftmost position where arr[left] >= target
Find the rightmost position of target.
int left = 0, right = arr.Length; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] <= target) left = mid + 1; else right = mid; } // left - 1 is now the rightmost position where arr[left-1] <= target
Not every problem needs binary search, but these signals suggest it might:
The most common bug in binary search is infinite loops. Here's how to prevent them: