Complexity of Binary Search | Dataford Interview Questions

What is the complexity of binary search?

Implement binary search for a sorted list of integers. Return the index of target if it exists, or -1 otherwise. Use an iterative approach and explain why each iteration discards half of the remaining search range.

Function: def binary_search(nums, target):

Input: nums is sorted in ascending order; target is an integer. Output: an integer index or -1.

Examples:

nums = [1, 3, 5, 7, 9], target = 7 returns 3 because 7 is at index 3.
nums = [2, 4, 6, 8], target = 5 returns -1 because 5 is absent.

Constraints: The list may be empty, values are sorted in ascending order, and duplicate values are not included.

Constraints

0 <= nums.length <= 10^5
nums is sorted in ascending order
nums contains no duplicate values
-10^9 <= nums[i], target <= 10^9

Function Signature

def binary_search(nums, target):

Your question is Complexity of 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