Explain Binary Search | Dataford Interview Questions

A Georgia Tech BuzzPort component stores record identifiers in ascending order. Given the sorted list 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. Do not use Python's built-in search or index methods.

Formal Specification

Implement binary_search(nums, target), where nums is a sorted list of integers in nondecreasing order and target is an integer. Return any valid index containing target; if the target does not occur, return -1.

Constraints

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
nums is sorted in nondecreasing order
Duplicate values may appear

Function Signature

def binary_search(nums, target):

Your question is Explain Binary Search. 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