First Bad Version

Siz mahsulot menejerisiz (Product Manager) va jamoangiz bilan yangi mahsulot yaratyapsiz. Afsuski, mahsulotning oxirgi versiyasi sifat tekshiruvidan (quality check) o'ta olmadi. Har bir versiya o'zidan oldingisiga asoslanganligi sababli, bitta yomon versiyadan keyingi barcha versiyalar yomon (bad) bo'ladi.

Sizda n ta versiya bor [1, 2, ..., n]. Birinchi yomon (bad) versiyani topishingiz kerak, qaysiki o'zidan keyingi barchasini yomon qilgan.

Sizda ma'lum versiyaning yomon yoki yo'qligini tekshirib beradigan isBadVersion(version) funksiyasi tayyor berilgan deb tasavvur qiling. API chaqiriqlarini imkon qadar kamaytirish uchun, yechimingiz Binary Search algoritmidan foydalanishi kerak.

Eslatma: Tizim testida biz isBadVersion funksiyasi o'rniga bad deb nomlangan versiyani parametrdan berib yuboramiz. Siz funksiyangiz ichida bad qaysi ekanligini izlashingiz kerak bo'ladi (ya'ni version >= bad bo'lsa u yomon versiya). Lekin O(log n) da ishlashi shart.

func solve(n int, bad int) int {
    // ...
}

Misollar

Input: n = 5, bad = 4
Output: 4
Tushuntirish:
isBadVersion(3) -> false
isBadVersion(5) -> true
isBadVersion(4) -> true
Demak 4 - birinchi yomon versiya.

Input: n = 1, bad = 1
Output: 1

Input: n = 10, bad = 1
Output: 1

Input: n = 100, bad = 73
Output: 73

Maslahatlar

1. Chiziqli qidiruv o'rniga, 'yomon versiyalar' har doim bitta chegaradan keyin boshlanishini hisobga olib binary search qo'llang.
2. lo=1, hi=n bilan boshlang, har safar mid'ni tekshirib, agar u yomon bo'lsa hi=mid qiling (yomon bo'lishi mumkin bo'lgan chegarani qisqartiring), aks holda lo=mid+1 qiling; lo==hi bo'lganda javob topiladi.