Problem Statement You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad....
Problem Statement Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity. Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4 Example 2: Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1 Solution class Solution: def search(self, nums: List[int], target: int) -> int: """ 0 1 2 3 4 5 ---------------------- / target -1, 0, 3, 5, 9, 12 ^a ^m ^b """ a, b = 0, len(nums) - 1 while a <= b: m = (b + a) // 2 if nums[m] == target: return m elif nums[m] < target: a = m + 1 else: b = m - 1 return -1 Leetcode 704 Binary Search