Binary Search From Scratch | Dataford Interview Questions

Your question is Binary Search From Scratch. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

The Medbridge exercise library stores exercise IDs in a sorted list so clinicians can locate content efficiently. Implement binary search from scratch to return the index of the first occurrence of a target ID.

The input list is sorted in nondecreasing order and may contain duplicate values. If the target does not exist, return -1.

Formal Specification

Implement binary_search(nums, target):

Input: nums, a list of integers sorted in nondecreasing order, and target, an integer.
Output: The zero-based index of the first element equal to target, or -1 if no matching element exists.
Do not use Python's built-in search, index, or sorting functions.
Use an iterative approach with O(1) auxiliary space.

Constraints

0 <= len(nums) <= 100000
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
nums is sorted in nondecreasing order

Function Signature

def binary_search(nums, target):