For people who suffered from binary search implementation details


  • 0
    O

    I've feel struggle for binary search questions for a long time, and I find a good article for helping me out. Based on the article, followings are how I solve the problem.

    • from [1, ... , n], after applying -guess() to all the elements, it's actually an array with value[-1, ..., 0, 1, ...., 1], ([0, 1,...1] if target is 1 and [-1, ,..., 0] if target is n) if we applied -guess(v)
      * the questions is somehow misleading, it should describes as guess(v) return -1 when you should lower your number.
    • Since there exist one and only one target in the array, we can actually write it in both lower and upper bound style.

    lower bound style

    when doing the lower bound style, after applying the predication function, you need to make the array looks like [false, false, ..., true, true, true...true], and you want to find the first true.

            low, high, predicate = 1, n, lambda v: -guess(v) >= 0
            bestSoFar = None
            while low <= high:
                v = low + (high - low) / 2
                if predicate(v):
                    bestSoFar = v
                    high = v - 1
                else:
                    low = v + 1
            return bestSoFar
    

    Upper Bound Style

    when doing the upper bound style, after applying the predication function, you need to make the array looks like [true, ..., true, false, ..., false], and you want to find the last true.

            low, high, predicate = 1, n, lambda v: -guess(v) <= 0
            bestSoFar = None
            while low <= high:
                v = low + (high - low) / 2
                if predicate(v):
                    bestSoFar = v
                    low = v + 1
                else:
                    high = v - 1
            return bestSoFar
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.