Account Login - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
1부터 n까지 버전중에 첫번쨰 잘 못된 버전을 찾는 문제. isBadversion 이 true가 되는 첫번째 n을 찾으면 된다.
1부터 n까지 binary search로 반으로 계속 쪼개면서 찾아가면 되겠다
보통 mid를 (left+ right)/2를 해서 왼쪽과 오른쪽수의 반을 찾아가도록 많이 한다. 하지만 이것은 overflow 를 발생할 수 있다. int형 변수의 범위가 2,147,483,647 이다. left =1, right = 2,147,483,647일때 left + right 했을때 int 범위를 넘을수가 있다. 언어마다 overflow가 될 수도 안 될수도 있지만 이것을 막기 위해 mid 를 left + (right-left)/2 로 구하자
func firstBadVersion(n int) int {
left,right := 1, n
for left < right {
mid := left + (right-left)/2
if isBadVersion(mid) {
right = mid
} else {
left = mid +1
}
}
return left
}