# The Half-Life Search

> Every guess cuts the problem in half.

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

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a sorted list of integers and a target, return the index of the target using binary search, or -1 if not found.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **binary search implementation**, the most fundamental divide-and-conquer algorithm. It probes whether a candidate can correctly manage the low/high pointers, compute the midpoint without overflow, and handle all termination conditions.

---

### Break down the requirements

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

Set `low = 0` and `high = len(nums) - 1`.

#### Step 2: Narrow the search space by halving

Compute `mid = (low + high) // 2`. Compare `nums[mid]` to the target and adjust `low` or `high` accordingly.

#### Step 3: Return the index or -1

If `nums[mid] == target`, return `mid`. If `low > high`, the target is not present.

---

### 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
    return -1
```

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

> **Interviewers Watch For**
>
> Whether you use `low <= high` (not `low < high`). The `<=` is necessary to check the final single-element range.

> **Common Pitfall**
>
> Setting `low = mid` or `high = mid` instead of `mid + 1` / `mid - 1`. This causes infinite loops when `low` and `high` are adjacent.

---

## Common follow-up questions

- How would you find the leftmost occurrence if duplicates exist? _(Tests continuing the search after finding a match by setting `high = mid - 1`.)_
- What is the overflow risk with `(low + high) // 2`? _(Tests knowledge that in languages with fixed-size integers, `low + (high - low) // 2` avoids overflow. Python has arbitrary precision, so it is not an issue.)_
- How would you search a rotated sorted array? _(Tests modified binary search with pivot detection.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_half_life_search)
- [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.