Binary Search and Complexity | Dataford Interview Questions

AgreeYa Solutions' delivery dashboard stores record identifiers in ascending order. Given a sorted list of integers and a target identifier, implement binary search to return the target's index, or -1 if it is absent.

Your algorithm must repeatedly compare the target with the middle element and discard the half that cannot contain the target.

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 one occurrence of target, or -1 when the target is not present.
Duplicate values may appear. Any valid index containing target is accepted.

Constraints

0 <= len(nums) <= 100000
-10^9 <= nums[i], target <= 10^9
nums is sorted in nondecreasing order
Return any valid index when duplicates exist

Function Signature

def binary_search(nums, target):

Your question is Binary Search and Complexity. Start with the requirements in the Question tab.

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

Problem