Binary Search Algorithm
Binary search is an efficient algorithm used to find an item in a sorted list by repeatedly dividing the search range in half.
Table of Contents
What is binary search?
Binary search is an efficient algorithm used to find an item in a sorted list by repeatedly dividing the search range in half. Algorithms are important for improving problem-solving skills, writing efficient programs, and preparing for coding interviews.
Before studying algorithms, it helps to understand basic programming concepts in Python or JavaScript.
How binary search Works
- Start with a list of values.
- Compare values against the target.
- Continue until the target is found or the search ends.
- Return the position or a message that the target was not found.
binary search in Python
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9], 7))binary search in JavaScript
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let 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;
}
console.log(binarySearch([1, 3, 5, 7, 9], 7));Time Complexity
| Case | Complexity |
|---|---|
| Best | O(1) |
| Average | O(log n) |
| Worst | O(log n) |
To understand performance better, read Time Complexity Explained and Big O Notation.
Common Mistakes
- Memorizing code without understanding the steps.
- Ignoring edge cases such as empty lists, duplicate values, and missing targets.
- Forgetting to test the algorithm with small and large input values.
- Confusing time complexity with actual running time on one computer.
- Using an advanced algorithm when a simple solution is enough.
Frequently Asked Questions
Is binary search important?
Yes. It helps programmers solve problems efficiently and understand how code performance changes with input size.
Should beginners learn algorithms?
Yes. Beginners should learn basic searching, sorting, recursion, and Big O notation after learning programming fundamentals.
Which language is best for learning algorithms?
Python is beginner-friendly, while JavaScript is useful for web developers. Both are good for learning algorithms.
Continue Learning
Algorithms Tutorial | Python Tutorial | JavaScript Tutorial | Big O Notation