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
Simple Binary Search

I have a very similar binary search solution with mid point defined as
mid = L + (RL)/2
to prevent potential overflow and an early stop conditionR  L > 1
since it is equivalent to find versionv
such thatisBadVersion(v1) = false
andisBadVersion(v) = true
.int firstBadVersion(int n) { int L = 0, R = n, mid; while (R  L > 1) if (isBadVersion(mid = L + (RL)/2)) R = mid; else L = mid; return R; }

@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!

@Ipeq1 One more reason to start using Python!
General description:
 Given a sorted array
vector<int> a
and an integert
, find the largest indexi
in range[first, last)
such thata[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+(RL)/2] <= t) L = mid; else R = mid; return L; // L can never be "last" }
 Given a sorted array

@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 :)