Recursive Binary Search
Updated
Problem statement
You are given an integer array nums sorted in increasing order with no repeated values, and an integer target. Return the index of target in nums. If target is not in nums, return -1.
Implement binary search using recursion: each call checks the middle element of the current range and then searches only the half that can still hold target. Your solution should run in O(log n) time.
Function
binarySearch(nums: int[], target: int) → intExamples
Example 1
nums = [-7,-2,0,4,9,15,21]target = 9return = 4Rounding the middle index down, the first middle element is nums[3] = 4. It is less than 9, so the search continues in indices 4 to 6. The middle of that range is nums[5] = 15, which is greater than 9, so only index 4 is left. Since nums[4] = 9, the answer is 4.
Example 2
nums = [2,4,6,8]target = 5return = -1The value 5 would sit between 4 and 6, but no element equals 5, so the answer is -1.
Example 3
nums = [42]target = 42return = 0The only element is the target, at index 0.
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i], target <= 10^4numsis sorted in strictly increasing order.
More EPAM interview questions
- Detect a Loop in a Linked ListONSITE INTERVIEW · Seen Oct 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Oct 2026
- Longest Palindromic SubstringPHONE SCREEN · Seen Oct 2026
- Container With Most WaterPHONE SCREEN · Seen Oct 2026
- Convert an Entry List to a MapPHONE SCREEN · Seen Oct 2026
- Count Array Element FrequenciesPHONE SCREEN · Seen Oct 2026
- Find First and Last Position of Element in Sorted ArrayPHONE SCREEN · Seen Oct 2026
- Group AnagramsPHONE SCREEN · Seen Oct 2026
- Longest Consecutive SequencePHONE SCREEN · Seen Oct 2026
- Max Consecutive Ones IIIPHONE SCREEN · Seen Oct 2026
Similar questions at other companies
- Roll a Weighted DieLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Implement Binary SearchQualys · ONSITE INTERVIEWQualys interview questions
- Messages in an Inclusive Timestamp RangeAttentive · PHONE SCREEN · ONSITE INTERVIEWAttentive interview questions
- Count Occurrences in a Sorted ArrayAdobe · PHONE SCREEN · ONSITE INTERVIEWAdobe interview questions
- Closest Version DateAmazon · ONSITE INTERVIEW
- Count Points in Each Boundary IntervalBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Find Unmet Users With Shared InterestsPalantir · ONSITE INTERVIEWPalantir interview questions
- Find Maximum Frequency of NumberGoogle · ONSITE INTERVIEWGoogle interview questions
- Song Duration Pairs Divisible by 60The Walt Disney Company · ONSITE INTERVIEWThe Walt Disney Company interview questions
- Numbers from One to N without LoopsAMD · ONSITE INTERVIEWAMD interview questions