Binary Search Implementation | Dataford Interview Questions

How would you implement binary search and explain its time complexity?

Implement binary_search(nums, target) for an ascending, sorted list of integers. Return the index of target if it exists, or -1 otherwise. If duplicate values are present, returning any matching index is valid. Use an iterative approach and explain why its time complexity is logarithmic.

Input: a sorted list nums and integer target.

Output: an integer index, or -1 when the target is absent.

Constraints

0 <= nums.length <= 100000
-10^9 <= nums[i], target <= 10^9
nums is sorted in nondecreasing order

Function Signature

def binary_search(nums, target):

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