(1) Binary Search: First Bad Version
I am Computer Science Graduate and Web Developer.
Question Link and Solution Link
Difficulty: Easy
Problem Statement: Given n we need to find a first bad version from 1 to n. Here we are given bool isBadVersion(version) this returns true if the version is bad and false if the version is good.
Observation: F F F F F F T T T T T, T T T T T T T T. This means once T will occur then it will occur till the end. F F F F F T T T F F F. This will never be the case. In simple terms, it means there will be continuous T or continuos F
Approach: Our correct answer will always be on the left side hence at last we will return the value of low.
int firstBadVersion(int n)
{
int low = 1, high = n, mid;
while (low < high)
{
mid = low + (high - low) / 2;
if (isBadVersion(mid)) high = mid;
else low = mid + 1;
}
return low;
}
Subscribe to the newsletter so that you never miss any post or update just like this one.
You can follow me on Hashnode for:
