# The Silent Locator

> Every lookup should cost you less than the one before it.

Canonical URL: <https://datadriven.io/problems/the_silent_locator>

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given a sorted list of integers and a target, return the index of target (any if duplicates) or -1 if not found. Use binary search; must run in O(log n).

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **binary search implementation from scratch**, one of the most fundamental algorithms in computer science. It probes whether a candidate can correctly manage the `low`, `high`, and `mid` pointers without off-by-one errors.

> **Trick to Solving**
>
> The key insight is narrowing the search space by half each iteration. Compare the middle element to the target: if it matches, return; if the target is smaller, search left; if larger, search right.

---

### Break down the requirements

#### Step 1: Initialize low and high pointers

Set `low = 0` and `high = len(nums) - 1` to cover the entire sorted list.

#### Step 2: Loop while the search space is valid

Continue while `low` is less than or equal to `high`. Compute `mid` as the average of low and high.

#### Step 3: Compare and narrow

If `nums[mid]` equals the target, return `mid`. If the target is smaller, set `high = mid - 1`. If larger, set `low = mid + 1`.

#### Step 4: Return -1 if not found

If the loop exits without a match, the target is not in the list.

---

### The solution

**Classic binary search with pointer narrowing**

```python
def binary_search(nums: list, target: int) -> int:
    low = 0
    high = len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    result = -1
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(log n) where n is the length of the list. The search space halves each iteration.
> 
> **Space:** O(1). Only three integer variables are maintained.

> **Interviewers Watch For**
>
> The `<=` in the while condition is essential. Using `<` skips the case where `low == high`, which is exactly when the target might be at the last remaining position.

> **Common Pitfall**
>
> Computing `mid = (low + high) // 2` can overflow in languages with fixed-width integers. In Python this is not an issue, but mentioning `low + (high - low) // 2` shows awareness of the classic bug.

---

## Common follow-up questions

- What if the list contains duplicates and you need the first occurrence? _(Tests modifying the algorithm to continue searching left after finding a match.)_
- How would you adapt this to find the insertion point? _(Tests understanding of bisect_left semantics.)_
- What if the list is too large to fit in memory? _(Tests knowledge of external search strategies and memory-mapped files.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_silent_locator)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.