Search in a Bitonic Array
Reported by candidates from Bloomberg's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Bloomberg reported this one in December 2020, and it's less scary than the title sounds. Search in a Bitonic Array is three binary searches wearing a trench coat. Find the peak, search the rising half, search the falling half. If you've got an OA invite and 48 hours, this is a pattern you can hold in your head. The catch is the O(log n) requirement, which kills any linear scan. StealthCoder sits as a quiet safety net during the live OA if your mind blanks on the peak search, but the logic here is short enough to own before you start.
The problem
nums contains distinct values, strictly increasing through one peak and strictly decreasing afterward. Return the index of target, or -1 if absent, in O(log n) time. Function searchBitonic(nums: int[], target: int) → int Examples Example 1 nums = [1,3,10,14,16,7,6,2] target = 3 return = 1 3 occurs on the increasing side. Constraints 1 <= nums.length <= 10^5.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is that the array has one peak, so you split the problem. First, binary search for the peak: compare nums[mid] with nums[mid+1]. If mid is smaller, the peak is to the right, so move lo to mid+1. Otherwise move hi to mid. When lo meets hi, that's the peak index. Then run a standard ascending binary search on [0, peak], and if it misses, a descending binary search on [peak+1, n-1] with the comparison flipped. The common pitfall is flipping the comparison wrong in the descending half, or using mid-1 on the peak search and skipping the peak itself. Values are distinct, so no plateau headaches. Total cost is O(log n) with O(1) space. If you freeze mid-assessment, StealthCoder can hand you the skeleton while you verify the boundaries yourself, but write the three loops by hand once tonight.
Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.
You can drill Search in a Bitonic Array cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Bloomberg's OA.
Bloomberg reuses patterns across OAs. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Search in a Bitonic Array FAQ
How hard is Search in a Bitonic Array really?+
Medium. The idea is simple once you see it, but off-by-one errors in the peak search trip people up. If you're comfortable with basic binary search, you can write this in about 15 minutes. The difficulty is in the details, not the concept.
What's the trick for the Bloomberg bitonic search?+
Reduce it to three binary searches. Find the peak by comparing nums[mid] to nums[mid+1], then search the increasing half normally and the decreasing half with a reversed comparison. Each step is O(log n), so the total stays logarithmic.
Can I just do a linear scan?+
No. The problem demands O(log n) and n goes up to 10^5. A linear scan might pass small tests but it ignores the stated requirement, and hidden tests or reviewers can flag it. Do the binary search version.
Is there a single-pass binary search version?+
Yes, but it's fiddly. You can compare against the target while deciding which side is monotonic, though the three-search approach is clearer and less error-prone. Under OA pressure, pick clarity. Fewer branches means fewer bugs.
How do I prepare for this in 48 hours?+
Write the peak finder from scratch until you stop second-guessing the lo/hi updates. Then write ascending and descending binary search templates. Test on edge cases: length 1, peak at the ends, target at the peak, target missing. Two hours is enough.