Divide and Conquer Search | Dataford Interview Questions

Use a divide-and-conquer algorithm to find elements in a sorted array.

Asked in the Onsite round 4 stage. Implement binary search for one target value.

Input and Output

Given a sorted list nums of integers and an integer target, return the index of target, or -1 if it is absent. If duplicates exist, return any valid index.

Example 1: nums = [1, 3, 5, 7, 9], target = 7 returns 3 because nums[3] == 7.

Example 2: nums = [2, 4, 6, 8], target = 5 returns -1 because 5 is not present.

Constraints

0 <= len(nums) <= 10^5
-10^9 <= nums[i], target <= 10^9
nums is sorted in nondecreasing order

Function Signature

def search_sorted_array(nums, target):

Your question is Divide and Conquer 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