Leetcode Note: Go - First Bad Version

First Bad Version - LeetCode
https://leetcode.com/problems/first-bad-version/

• Go 言語で取り組んだメモ

所感

• 数値を isBadVersion で判定して、小さい値を探して return する

• 愚直に実装すると下記のようになるが、これだと制限時間内で処理が完了しないため、アルゴリズムを改良する必要がある

  /** 
  * Forward declaration of isBadVersion API.
  * @param   version   your guess about first bad version
  * @return 	 	      true if current version is bad 
  *			          false if current version is good
  * func isBadVersion(version int) bool;
  */
  
  func firstBadVersion(n int) int {
  for i := 1; i < n; i++ {
      if isBadVersion(i) == true {
          return i
      }
  }
  return n
  }

回答

Go Benchmarking and profiling different versions - LeetCode Discuss
https://leetcode.com/problems/first-bad-version/discuss/1778578/Go-Benchmarking-and-profiling-different-versions

/** 
 * Forward declaration of isBadVersion API.
 * @param   version   your guess about first bad version
 * @return 	 	      true if current version is bad 
 *			          false if current version is good
 * func isBadVersion(version int) bool;
 */

func firstBadVersion(n int) int {
	start := 0
	end := n

	for mid := (end + start) / 2; start < end; mid = (end + start) / 2 {
		if isBadVersion(mid) {
			end = mid
		} else {
			start = mid + 1
		}
	}

	return start
}

• for ループの回し方をバイナリサーチに変更
  • 中心の値からカウンタを始めて、更に中心の値を走査していく