Algorithms02.01.2025
The Battle of 3 Kings - Binary Search vs Hashmap vs Linear Search
When dealing with a dataset, sometimes the most important thing is to find the data as quickly as possible. Sometimes this means sacrificing memory and sometimes performance.In this article we will make a brief comparison of 3 data search algorithms for 1M (1.000.000) entries.1 - Use a Hashmap (Best for Fast Exact Matches)
When to Choose
- You need exact match searches (e.g., "Does this exact string exist?").
- Searches are frequent (e.g., user types a query in real-time).
- You can afford extra memory (~40-100 MB for 1M entries).
Pros
- Lookup Time: O(1) (instant after hashmap creation).
- Setup Time: O(n) (one-time cost).
- Dynamic Data: Supports quick additions/removals (unlike sorted arrays).
Cons
- Memory overhead (duplicates keys).
- Only works for exact matches, not substrings or ranges.
Example
// Preprocess onceconst hashMap = new Map();
// Use a unique key like "id"
data.forEach(item => hashMap.set(item.id, item));
// Real-time search
const result = hashMap.get(userInput);
2 - Sort + Binary Search (Best for Memory Efficiency)
When to Choose
- You need exact or range-based searches.
- Memory is tight (no extra overhead).
- Data is static (no frequent additions/removals).
Pros
- Lookup Time: O(log n) (fast for large data).
- Memory: No extra memory beyond the sorted array.
Cons
- Setup Time: O(n log n) (sorting cost).
- Dynamic Data: Adding/removing elements requires re-sorting (O(n)).
Example
// Sort once - Sort by keyconst sortedData = [...data].sort((a, b) => a.id.localeCompare(b.id));
// Binary search function
function binarySearch(arr, target) {
let low = 0, high = arr.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (arr[mid].id === target) return arr[mid];
else if (arr[mid].id < target) low = mid + 1;
else high = mid - 1;
}
return null;
}
// Usage
const result = binarySearch(sortedData, userInput);
3 - Linear Search (Avoid for Large Data)
When to Choose
- You search rarely (e.g., once).
- Data is tiny (e.g., <10.000 entries).
Pros
- No setup time.
- Simple to implement.
Cons
- Lookup Time: O(n) (unbearably slow for 1M entries).
Example
// Avoid this for large data!const result = data.find(item => item.id === userInput);
Conclusion
- For Exact Matches: Hashmap is the clear winner (speed trumps memory for large data).
- For Range Queries or Memory Constraints: Sort the data and use binary search.
- Never Use Linear Search for 1M entries unless you have no other choice.
Master programming languages like JavaScript, Typescript, design materials about HTML, CSS and Algorithms, through expert tutorials, software development best practices, and hands-on coding challenges for web development, app creation, and code optimization. Stay ahead in tech with cutting-edge insights on frameworks like React and Node.js, debugging techniques, and the latest industry trends to boost your coding skills and career growth in software engineering. Join a thriving developer community exploring AI, machine learning, and cloud computing while preparing for coding interviews and building scalable, efficient software solutions.