Loading W Code...
Linear Search, Binary Search, Bounds, Rotated Array Search & more.
Imagine looking for a specific document on your computer. You could open and inspect every single folder manually, or you could type the filename into a search indexer that points you directly to the file's path.
Searching is the algorithmic process of locating a target element or record within a collection of data.
O(1) access times.#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
int target = 5;
// Using STL find (Linear Search)
auto it = find(arr.begin(), arr.end(), target);
if (it != arr.end()) {
cout << "Found at index: " << (it - arr.begin()) << endl;
}
// Using STL binary_search (needs sorted array)
sort(arr.begin(), arr.end());
bool found = binary_search(arr.begin(), arr.end(), target);
cout << "Binary search found: " << (found ? "Yes" : "No") << endl;
return 0;
}Imagine searching for a business card in an unsorted pile on your desk. You inspect each card one-by-one starting from the top, stopping only when you find the target card or reach the bottom of the pile.
Linear Search checks every element in the data structure sequentially until a match is found or the end is reached.
O(n) worst-case time, making it slow for large datasets.In a standard search loop, we check two conditions per iteration: whether we have reached the end of the array, and whether the current element matches our target. By replacing the last element with our target (the sentinel value), we can remove the boundary check inside the loop, reducing instruction count.
#include <iostream>
#include <vector>
using namespace std;
// Basic Linear Search
int linearSearch(vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == target) {
return i; // Found at index i
}
}
return -1; // Not found
}
// Sentinel Linear Search (slightly optimized)
int sentinelSearch(vector<int> arr, int target) {
int n = arr.size();
int last = arr[n - 1]; // Save last element
arr[n - 1] = target; // Place sentinel
int i = 0;
while (arr[i] != target) {
i++;
}
arr[n - 1] = last; // Restore last element
if (i < n - 1 || arr[n - 1] == target) {
return i;
}
return -1;
}
// Find all occurrences
vector<int> findAll(vector<int>& arr, int target) {
vector<int> indices;
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == target) {
indices.push_back(i);
}
}
return indices;
}
// Search in 2D array
pair<int, int> search2D(vector<vector<int>>& matrix, int target) {
for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[i].size(); j++) {
if (matrix[i][j] == target) {
return {i, j};
}
}
}
return {-1, -1};
}
int main() {
vector<int> arr = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170};
int target = 110;
int result = linearSearch(arr, target);
if (result != -1) {
cout << "Found at index: " << result << endl; // 6
}
return 0;
}Imagine looking up a word in a printed dictionary. You open the book to the middle. If your word starts with a letter that comes alphabetically earlier, you discard the entire right half of the book and repeat the process on the remaining left half.
Binary Search is an optimal O(log n) algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.
mid = left + (right - left) / 2 to avoid integer overflow bugs.#include <iostream>
#include <vector>
using namespace std;
// Iterative Binary Search
int binarySearch(vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Prevents overflow
if (arr[mid] == target) {
return mid; // Found
}
if (arr[mid] < target) {
left = mid + 1; // Search right half
} else {
right = mid - 1; // Search left half
}
}
return -1; // Not found
}
// Recursive Binary Search
int binarySearchRecursive(vector<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);
}
int main() {
vector<int> arr = {2, 3, 4, 10, 40, 50, 60, 70};
int target = 10;
int result = binarySearch(arr, target);
cout << "Found at index: " << result << endl; // 3
return 0;
}In sorted arrays with duplicate values, standard binary search may return any of the matching indices. To find the exact boundaries of a value range, we use lower and upper bound variations:
≥) the target.>) the target.The number of times an element occurs in a sorted array is easily computed as:
count = upperBound(target) - lowerBound(target)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Lower bound: First position where arr[i] >= target
int lowerBound(vector<int>& arr, int target) {
int left = 0, right = arr.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
// Upper bound: First position where arr[i] > target
int upperBound(vector<int>& arr, int target) {
int left = 0, right = arr.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
// Count occurrences using bounds
int countOccurrences(vector<int>& arr, int target) {
int lb = lowerBound(arr, target);
int ub = upperBound(arr, target);
return ub - lb;
}
int main() {
vector<int> arr = {1, 2, 2, 2, 3, 4, 5};
int target = 2;
cout << "Lower bound of 2: " << lowerBound(arr, target) << endl; // 1
cout << "Upper bound of 2: " << upperBound(arr, target) << endl; // 4
cout << "Count of 2: " << countOccurrences(arr, target) << endl; // 3
return 0;
}Binary search is not limited to finding elements in arrays. It can also search over a range of integers representing potential answers.
If we can define a search range [min_possible, max_possible] and write a validation function isValid(value) that runs in O(n) or O(1) time, we can binary search the answer:
mid = (low + high) / 2.isValid(mid) is true, save mid as a candidate answer and shrink the range to look for better solutions.When a sorted array is rotated (e.g., [4, 5, 6, 7, 0, 1, 2]), at least one half of the array (left or right) is guaranteed to remain sorted. We check which half is sorted, determine if our target lies within its boundaries, and adjust our binary search pointers accordingly.
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// Square root using binary search
int mySqrt(int x) {
if (x < 2) return x;
long left = 1, right = x / 2;
while (left <= right) {
long mid = left + (right - left) / 2;
long square = mid * mid;
if (square == x) return mid;
if (square < x) left = mid + 1;
else right = mid - 1;
}
return right; // Floor of sqrt
}
// Find peak element (element greater than neighbors)
int findPeak(vector<int>& arr) {
int left = 0, right = arr.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < arr[mid + 1]) {
left = mid + 1; // Peak is on right
} else {
right = mid; // Peak is on left (including mid)
}
}
return left;
}
// Search in rotated sorted array
int searchRotated(vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
// Check which half is sorted
if (arr[left] <= arr[mid]) { // Left half is sorted
if (target >= arr[left] && target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else { // Right half is sorted
if (target > arr[mid] && target <= arr[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
int main() {
cout << "sqrt(16) = " << mySqrt(16) << endl; // 4
vector<int> arr1 = {1, 2, 3, 4, 5, 3, 1};
cout << "Peak at index: " << findPeak(arr1) << endl; // 4
vector<int> arr2 = {4, 5, 6, 7, 0, 1, 2};
cout << "Found 0 at: " << searchRotated(arr2, 0) << endl; // 4
return 0;
}We can search sorted 2D grids efficiently using two different methods depending on how the grid is structured:
Each individual row and column is sorted, but the first element of a row might be smaller than the last element of the previous row (e.g., diagonal gradients).
O(row + col) time.The last element of each row is strictly smaller than the first element of the next row.
row * col. Perform standard binary search. To map a flat index mid back to 2D coordinates, use:
r = mid / cols and c = mid % cols.#include <iostream>
#include <vector>
using namespace std;
// Type 1: Row-wise and column-wise sorted
// Staircase search - O(m + n)
bool searchMatrix1(vector<vector<int>>& matrix, int target) {
if (matrix.empty()) return false;
int m = matrix.size();
int n = matrix[0].size();
// Start from top-right corner
int row = 0, col = n - 1;
while (row < m && col >= 0) {
if (matrix[row][col] == target) {
cout << "Found at (" << row << ", " << col << ")" << endl;
return true;
}
if (matrix[row][col] > target) {
col--; // Move left
} else {
row++; // Move down
}
}
return false;
}
// Type 2: Fully sorted matrix (treat as 1D array)
// Binary search - O(log(m*n))
bool searchMatrix2(vector<vector<int>>& matrix, int target) {
if (matrix.empty()) return false;
int m = matrix.size();
int n = matrix[0].size();
int left = 0, right = m * n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// Convert 1D index to 2D
int row = mid / n;
int col = mid % n;
if (matrix[row][col] == target) {
cout << "Found at (" << row << ", " << col << ")" << endl;
return true;
}
if (matrix[row][col] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
int main() {
vector<vector<int>> matrix1 = {
{10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}
};
cout << "Matrix 1 - ";
searchMatrix1(matrix1, 29); // Found at (2, 1)
return 0;
}