To all my dear fellow Leetcoders. If you see a binary search question in an interview buckle up. There are good chances of bombing the interview if not careful. Binary search is a freaking gold mine for all cornor cases. I bombed an interview with Amazon a month ago. The question was to find an element in rotated sorted array. All the interview went like this while time is still there: write code cornor case from interviewer code fails I called it bloody because there is no way to imagine how low and high behave at cornor cases. Ever since that interview, whenever I see a binary search question in Leetcode, I close my eyes relax and try to get accepted in one shot (Never happened though) Edit: Thanks a lot to the community for sharing hell lot of useful techniques in the comments
The corner cases on the rotated array always messes things up
Exactly and not just that question
That one question costed me a job at Microsoft when I desperately needed one.
I had to revisit those particular set of 4-5 questions about 10 times each to completely grasp the logic. It's not very hard but sure is tricky and easy to get wrong. But once you get it you don't mess it up. I recommend revisiting these Find element in rotated array, find min in rotated array, find min in rotated array with duplicates, find element in rotated array with duplicates till they are a cakewalk for you.
Exactly
The best way to find bugs in a binary search algo is to test for [True, false] and [false, true] cases
There's an easy way to do binary search without bloody corner cases. Start with linear search and slap an outer loop on top:
just memorise binary search
The textbook version is a gold mine for corner cases as OP alluded. Especially when you try to adopt it for a bit non standard problem. And you're not really going to memorize a dozen of variations of it
So much this. Few leetcode hards can fuck me, but binary search does every time, unless it's the standard one. Even stupid things like find the rightmost element x in a sorted array with dublicates.
Just memorize the template.... Low, high = 0, Len(arr) - 1 While low <= high: Mid = low + (high - low) // 2 If arr[mid] == target: Return mid Elif arr[mid] > target: High = mid - 1 Else: Low = mid + 1 Return -1
I memorized a couple standard templates. But none of them work for today’s leetcode problem. That template you gave can be used for “binary search implementation” not for variations
So first you make sure that the array is actually rotated. You can do that by comparing the first element with the last element in the array (make sure that it is strictly less than the last, if not, then one binary search will suffice). Then, do one binary search to find the rotation point. Then, if the target is greater than the first element in the array, then do a binary search with low = 0, high = rotation point - 1. Else if target < first element in arr, do a binary search with low = rotation, high = len(arr) - 1 Obv, it’s still log n runtime & o(1) space despite the two while loops.
There's a binary search section in 'explore tab' on LC. Pretty impressive stuff with 3 kinds of templates.
sbeuiedbfowkwbuzka.... I can’t believe I never clicked on the explore tab before. The stuff here is so useful
It sounds like you just need a bit of practice. I would be skeptical of giving any interviews if you can’t solve variations of binary search in sleep.
Google 'invariants for binary search' and understand how it works. There are basically two invariants, either the ans lies in [s,e] or ans lies in [s,e). Once you'll understand these rest assured any binary search problem (search in circular array, finding floor/ceil, pivot in circular array, h-index, split array max sum etc.) would be a breeze.
Thanks for sharing :)
Binary search is easy af, DP is the real shit
lol dp is 0 or 1. You either solve it or not. There’s nothing between
I feel like dp is hard to reason, easy to code. Binary search is easy to reason, hard to code.