Binary Search in Sorted Logs

EasyPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Binary Search in Sorted Logs. 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.

You need to log in / sign up to run or submit.

Problem

At Google, security systems often search sorted event IDs or rule identifiers quickly. Write a function that uses binary search to find a target integer in a sorted array.

Return the index of target if it exists in the array. If it does not exist, return -1.

Formal Specification

Input:
- nums: a list of integers sorted in ascending order
- target: an integer to search for
Output:
- An integer index of target in nums, or -1 if not found

Your solution should run in O(log n) time.

Constraints

0 <= len(nums) <= 10^5
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
nums is sorted in strictly increasing order
Expected time complexity is O(log n)

Function Signature

def binary_search(nums, target):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output