# Simple Binary Search

• ``````class Solution(object):
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
``````

• 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;
}
``````

• @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 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"
}
``````

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

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