Binary Search Practice Problem
This data science coding problem helps you practice Sorting & Searching, binary search, and implementation skills. Read the problem statement, write your solution, and strengthen your understanding of Sorting & Searching.
- Problem ID: 101
- Problem key: 101-binary-search
- URL: https://datacrack.app/solve/101-binary-search
- Difficulty: easy
- Topic: Sorting & Searching
- Module: Python Fundamentals
Problem Statement
# 🧩 Binary Search
---
### 🎯 Goal
Binary search is the most important algorithm to understand O(log n) thinking. Instead of checking every element (O(n)), it repeatedly halves the search space — making it orders of magnitude faster on sorted data. The same principle powers indexed lookups in databases and model hyperparameter search.
---
### 🔍 The Algorithm
On a **sorted** list, at each step:
1. Look at the **middle** element.
2. If it matches the target → return its index.
3. If target is smaller → search the **left half**.
4. If target is larger → search the **right half**.
5. If search space is empty → target not found, return -1.
---
### 💻 Task
Implement `binary_search(nums, target)` iteratively.
---
### 📥 Input
- `nums`: list of integers sorted in **ascending order**
- `target`: int — the value to find
### 📤 Output
- int — the index of `target` in `nums`, or `-1` if not found
---
### 🧩 Starter Code
```python
def binary_search(nums, target):
"""
Search for target in a sorted list using binary search.
Args:
nums (list[int]): Sorted list of integers
target (int): Value to find
Returns:
int: Index of target, or -1 if not found
"""
left, right = 0, len(nums) - 1
while left <= right:
# 🧠 TODO: Compute mid = (left + right) // 2
# 🧠 TODO: Compare nums[mid] to target
# 🧠 TODO: Narrow search range based on comparison
pass
return -1
```
---
### 💡 Example
```python
binary_search([1, 3, 5, 7, 9, 11, 13], 7) # Expected: 3
binary_search([1, 3, 5, 7, 9, 11, 13], 4) # Expected: -1
```
---
Starter Code
def binary_search(nums, target):
"""
Search for target in a sorted list using binary search.
Args:
nums (list[int]): Sorted list of integers
target (int): Value to find
Returns:
int: Index of target, or -1 if not found
"""
left, right = 0, len(nums) - 1
while left <= right:
# 🧠 TODO: Compute mid = (left + right) // 2
# 🧠 TODO: Compare nums[mid] to target
# 🧠 TODO: Narrow search range based on comparison
pass
return -1