Leetcode: First Bad Version

Leetcode — First Bad Version

First Bad Version is tagged as an easy question on Leetcode. First Bad Version - LeetCode

Problem Statement:

The problem states that there is a bad release on version control (git, svn, etc). Your task is to write code to find the first bad version, given an “API” that gives you the bad version. There is a similar tool in git called **git-bisect**.

Examples:

Constraints:

Brainstorm:

**Input: **n ( The number of versions we have )

Output: The first bad version

The brute force approach to solve this is to check if each version is bad, looping through versions 1 through n and passing the version to isBadVersion.

This is ok for a small amount versions, but it will take a lot more time when there are a lot of versions. A more efficient way to do this is to take advantage of the fact that the versions are in order or sorted. We can take a **binary search** approach.

1. The left pointer is 1 since all versions start there.

2. The right pointer will be n or the number of versions.

3. We will have a while loop to try to find the first bad version as long as we haven’t gone through all of the versions already.

4. Get the mid-point. Right minus left would give us the number of versions between left and right. We divide by two to git a mid-point. We also add left to this to handle integer overflows.

5. If mid is a bad version. If it is a bad version, we can move right to mid’s position. If mid is a bad version every version after mid will be a bad version. We don’t want to waste time checking anything past mid.

6. If mid is not a bad version, we can move left up one to try to find the next bad version between left and right

7. Return left. Left and right will eventually be next to each other, which we will then exit the loop. The left version will be the firstBadVersion.

Solution:

{% gist https://gist.github.com/cmcoffeedev/1192b325524b9ce26c412baf6ed59535.js %} Thank you for taking the time to read my article!