First bad version | Leetcode #278

This video explains a very important searching algorithm problem which is to find the first bad version in an array. We are not actually given the array but we can make API calls to find a particular array element is good or bad. Our goal is to minimize the API calls and find out the first bad version from left. I have shown the solving idea, intuition and similar problem which will help this solve this problem. I have shown proper example and solved it using binary search. The end of the video contains CODE explanation for the algorithm and CODE LINK is given below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

SIMILAR PROBLEM:-

[dev-skills]

to prevent overflow use the statement as below in line 14 of in your solution code -->
mid = low + ( high - low ) / 2;

[ahmadmtera]

Happy to say I got to it before watching the video so it was satisfying to see that our solutions matched!

As requested, here's my solution in Java:

public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int badVersionNumber = n; // The first candidate for the bad version is the last one (given). This is contested (& updated if there's an earlier version) below.
int left = 0, right = n;

while(left <= right) {
int middle = left + (right - left) / 2;
boolean isBad = isBadVersion(middle);
if(isBad) { // Update candidate & look for smaller bad version (if exists)
badVersionNumber = middle;
right = middle - 1;
} else // Look to the right since all versions from middle to the left are good
left = middle + 1;
}
return badVersionNumber;
}

[oxanasf]

Perfect, it was concise and clear at the same time. Even though I am not familiar with the sintax, I was able to understand everything.

[sharuksk]

Super explanation bro.Thanks a lot.Keep helping

[abhinavpandey]

Actually start +end is becoming greater than int range so we can make all variables as long n can typecast it as req . For sol to b accepted

[cosmoatlas]

This solution works but it exceeds some of the time limits in the testing cases.

[subham-raj]

Why (low + high) ain't triggering integer overflow for you? It was triggering for me. I solved it by (low + (high - low) / 2). Can you please explain. Does C++ handles the integer overflow?

[sonalpriya]

public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int start = 0;
int end = n;

while(start<=end){
int mid = start+ (end-start)/2;
boolean isBad=isBadVersion(mid);
if(isBad==true){
end=mid-1;
}
else{
start=mid+1;
}

return start;
}
}
return -1;



}
}

[suhalvemu]

I have a doubt -- in the input it is given as 'int n' but we are returning as 'long int'. in my local I got warnings but solution got accepted. is it genuinely designed that way or was it as design mistake?

[kanishkagupta]

I made a small change in the solution.
int firstBadVersion(int n) {
bool m;
int i=1;
int j=n;
int mid;
while(i<=j)
{
mid=i+(j-i)/2;
if(isBadVersion(mid))
{

return mid;
else
return mid;
}
if(isBadVersion(mid))
j=mid-1;
else
i=mid+1;
}
return mid;
}

[venkateshthirunagiri]

After solving this problem at my first sight I decided to make videos like you....
😜😜😜😜
So which software you are using to write like that....

[emilyhuang]

Why did you initiate high to n instead of n-1 ?

[codoholic]

Which software is you are using to explain this stuff?

[adityahpatel]

Nowhere in the world a python list starts from index 1. you must explain why you changed the worldly order by making list start from index 1

[pritam_one]

returning high+1 also gives ans no need for result

[nikhilbadyal]

C++

class Solution {
public:
int firstBadVersion(int n){
int start = 1 ;
int end = n;
int last_one = -1 ;
while(end>= start){
int mid = start + (end-start)/2;
if(isBadVersion(mid)){
last_one = mid ;
end = mid -1;
}else{
start = mid + 1;
}
}
return last_one ;
}
};

[shoebkhan-mwym]

getting time limit exceeded, with this algorithm.

[cipherCrafters]

Sir please tell me which writing board you use for writing

[syedkaja]

i=0;
while(i<=n)
{
if(isbadversion(i))
{return i;}
i++;
}
can we try like this

[ferringxor]

@TECH DOSE you're masterstroke . By the way one question how will come to conclusion that we aplly binary search algo in this question