ORID29

今天看到leetcode上面有个人的分享很有用，我就写下来了。
The key point for any binary search is to figure out the "Search Space". For me, I think there are two kind of "Search Space" -- index and range(the range from the smallest number to the biggest number). Most usually, when the array is sorted in one direction, we can use index as "search space", when the array is unsorted and we are going to find a specific number, we can use "range".

原文链接在这里

第一次参加周赛，感觉比我想象的要好，答对了两道题。第三题有了思路但是没做完，主要是真的没想到这是一道binary search的问题，然后自己就回去回顾了一下binary search问题的要点。我发现有个人说得很好。
The key point for any binary search is to figure out the "Search Space". For me, I think there are two kind of "Search Space" -- index and range(the range from the smallest number to the biggest number). Most usually, when the array is sorted in one direction, we can use index as "search space", when the array is unsorted and we are going to find a specific number, we can use "range".
也就是说这道题其实也是给了你一个range，然后让你从这个range里面找到最小的一个天数，满足能够提供酒宴的标准。虽然这个list没有被排序，但是你从他给你的range(1-10^9) 里面开始binary search，每一次search的时候，看当前天数是否满足条件（有足够相邻的花能够提供给晚宴），如果满足，update min value。直到start < end 为止。 我当时做这道题已经把判断条件写好了，用O（N）来判断当前天数是否满足晚宴要求，但是我在搜寻最小天数的时候进入了误区，就是我是按照给你的list里面每一个数去试的，导致我搜最小天数会是O（N^2），因为每个数我要从list 里面找出来，然后在重新开一个list把开花的院子标记为0，这样你list里面每一个数都要把整个list走一遍（标记开花的地方为0），所以导致了我的答案TLE。然后看到了别人给出的答案，我才发现原来用O（logN） 就可以解决……