Simple Binary Search


  • 0
    class Solution(object):
        def firstBadVersion(self, n):
                left, right = 1, n
                while left < right:
                    status = isBadVersion( (left + right) >> 1)
                    left, right = left if status else ((left + right) >> 1) + 1, right if not status else (left + right) >> 1
            return left
    

  • 0

    I have a very similar binary search solution with mid point defined as mid = L + (R-L)/2 to prevent potential overflow and an early stop condition R - L > 1 since it is equivalent to find version v such that isBadVersion(v-1) = false and isBadVersion(v) = true.

        int firstBadVersion(int n) {
          int L = 0, R = n, mid;
          while (R - L > 1) if (isBadVersion(mid = L + (R-L)/2)) R = mid; else L = mid;
          return R;
        }
    

  • 0

    @zzg_zzm it's good to know that return right seems to stop earlier than left! BTW, Python is safe for big integer calculation. Do you mean to find the first appearance element by using your code? If so, I'm really curious to know how to find the last appearance using the same style!


  • 1

    @Ipeq1 One more reason to start using Python!

    General description:

    • Given a sorted array vector<int> a and an integer t, find the largest index i in range [first, last) such that a[i] <= t.

    Note that index last is excluded from the range. Assume [first, last) is a valid range. (similar to http://www.cplusplus.com/reference/algorithm/upper_bound/)

    int upperBound(vector<int>& a, int first, int last, int t) {
      int L = first, R = last, mid;
      while (R - L > 1) if (a[mid=L+(R-L)/2] <= t) L = mid; else R = mid;
      return L; // L can never be "last"
    }
    

  • 0

    @zzg_zzm Binary search is an easy understanding algorithm, but so many detailed tricks here, no wonder it's been 16 years from the publish of the algorithm to the first binary search that works correctly for all values of n appears! I miss quiet quiet :-)


Log in to reply
 

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