Master search algorithms from linear to exponential, with complexity analysis, optimization techniques, and real-world applications. Includes implementations for both sorted and unsorted data.
Searching Algorithms: Complete Guide
Search Algorithm Usage (2023)
1. Fundamental Search Algorithms
Linear Search
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}Complexity: O(n) time, O(1) space
Use When: Unsorted or small datasets
Binary Search
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}Complexity: O(log n) time, O(1) space
Use When: Sorted arrays
Time Complexities
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Linear | O(1) | O(n) | O(n) | O(1) |
| Binary | O(1) | O(log n) | O(log n) | O(1) |
| Jump | O(1) | O(√n) | O(√n) | O(1) |
| Exponential | O(1) | O(log i) | O(log n) | O(1) |
2. Advanced Search Techniques
Jump Search
function jumpSearch(arr, target) {
const n = arr.length;
const blockSize = Math.floor(Math.sqrt(n));
let prev = 0;
let step = blockSize;
while (arr[Math.min(step, n) - 1] < target) {
prev = step;
step += blockSize;
if (prev >= n) return -1;
}
while (arr[prev] < target) {
prev++;
if (prev === Math.min(step, n)) return -1;
}
return arr[prev] === target ? prev : -1;
}Optimal Block: √n
Use When: Sorted arrays, better than linear
Exponential Search
function exponentialSearch(arr, target) {
if (arr[0] === target) return 0;
let i = 1;
while (i < arr.length && arr[i] <= target) {
i *= 2;
}
return binarySearch(arr, target, i/2, Math.min(i, arr.length));
}Combines: Exponential + Binary
Use When: Infinite/unbounded arrays
Specialized Searches
Interpolation Search
function interpolationSearch(arr, target) {
let low = 0, high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
const pos = low + Math.floor(
((target - arr[low]) * (high - low)) /
(arr[high] - arr[low])
);
if (arr[pos] === target) return pos;
if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}Complexity: O(log log n) avg
Use When: Uniformly distributed data
Ternary Search
function ternarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const mid1 = left + Math.floor((right - left) / 3);
const mid2 = right - Math.floor((right - left) / 3);
if (arr[mid1] === target) return mid1;
if (arr[mid2] === target) return mid2;
if (target < arr[mid1]) right = mid1 - 1;
else if (target > arr[mid2]) left = mid2 + 1;
else {
left = mid1 + 1;
right = mid2 - 1;
}
}
return -1;
}Comparisons: More than binary
Use When: Finding min/max in unimodal functions
3. Search in Data Structures
Hash Tables
class HashTable {
constructor(size = 53) {
this.keyMap = new Array(size);
}
_hash(key) {
let total = 0;
const PRIME = 31;
for (let i = 0; i < Math.min(key.length, 100); i++) {
const char = key[i];
const value = char.charCodeAt(0) - 96;
total = (total * PRIME + value) % this.keyMap.length;
}
return total;
}
search(key) {
const index = this._hash(key);
if (this.keyMap[index]) {
for (let i = 0; i < this.keyMap[index].length; i++) {
if (this.keyMap[index][i][0] === key) {
return this.keyMap[index][i][1];
}
}
}
return undefined;
}
}Complexity: O(1) avg
Use When: Fast lookups needed
Binary Search Trees
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
search(value, node = this.root) {
if (!node) return false;
if (value === node.value) return true;
if (value < node.value) return this.search(value, node.left);
return this.search(value, node.right);
}
}Complexity: O(h) time
Balanced: O(log n) height
Search Algorithm Cheat Sheet
| Scenario | Best Algorithm | Time Complexity |
|---|---|---|
| Unsorted small array | Linear Search | O(n) |
| Sorted array | Binary Search | O(log n) |
| Unbounded array | Exponential Search | O(log i) |
| Uniform distribution | Interpolation Search | O(log log n) |
| Key-value pairs | Hash Table | O(1) |
4. Real-World Applications
Database Indexing
B-Trees: Balanced search trees for disk-based storage
// Simplified B-tree search
function bTreeSearch(node, key) {
let i = 0;
while (i < node.keys.length && key > node.keys[i]) i++;
if (i < node.keys.length && key === node.keys[i]) return node.values[i];
if (node.isLeaf) return null;
return bTreeSearch(node.children[i], key);
}Autocomplete Systems
Trie Search: Prefix-based string searching
class TrieNode {
search(word) {
let node = this.root;
for (const char of word) {
if (!node.children[char]) return false;
node = node.children[char];
}
return node.isEnd;
}
}Geospatial Data
Quadtree/K-d Tree: Nearest neighbor searches
function nearestNeighbor(node, point, best = null) {
if (!node) return best;
const dist = distance(node.point, point);
if (!best || dist < distance(best, point)) best = node.point;
const axis = node.depth % 2;
const nextBranch = point[axis] < node.point[axis] ? node.left : node.right;
return nearestNeighbor(nextBranch, point, best);
}Search Algorithm Selection Guide
✓ Unsorted data → Linear or Hash Table
✓ Sorted arrays → Binary Search
✓ Unknown size → Exponential Search
✓ Uniform data → Interpolation Search
✓ Frequent lookups → Hash Table
Pro Tip: Modern systems combine multiple search techniques. For example, databases use B-trees (logarithmic search) with hash indexes for exact matches. Always consider your data characteristics before choosing an algorithm.
0 Interaction
0 Views
0 Likes
×
