278. First Bad Version(二分查找)

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.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version. 

 1 bool isBadVersion(int version);
 2
 3 class Solution {
 4 public:
 5     int firstBadVersion(int n) {
 6         int low = 1;
 7         int high = n;
 8         int res = 0;
 9         while(low < high) {
10             int mid = low + (high - low) / 2;
11             if(isBadVersion(mid)) {
12                 high = mid;
13             } else {
14                 low = mid+1;
15             }
16         }
17         return high;
18     }
19 };
 

原文地址:https://www.cnblogs.com/zle1992/p/12578531.html

时间: 03-26

278. First Bad Version(二分查找)的相关文章

Leetcode 278 First Bad Version 二分查找

题意:找到第一个出问题的版本 二分查找,注意 mid = l + (r - l + 1) / 2;因为整数会溢出 1 // Forward declaration of isBadVersion API. 2 bool isBadVersion(int version); 3 4 class Solution { 5 public: 6 int firstBadVersion(int n) { 7 int l = 1, r = n , ans ; 8 while(l <= r){ 9 int m

二分查找总结

最近刷leetcode和lintcode,做到二分查找的部分,发现其实这种类型的题目很有规律,题目大致的分为以下几类: 1.最基础的二分查找题目,在一个有序的数组当中查找某个数,如果找到,则返回这个数在数组中的下标,如果没有找到就返回-1或者是它将会被按顺序插入的位置.这种题目继续进阶一下就是在有序数组中查找元素的上下限.继续做可以求两个区间的交集. 2.旋转数组问题,就是将一个有序数组进行旋转,然后在数组中查找某个值,其中分为数组中有重复元素和没有重复元素两种情况. 3.在杨氏矩阵中利用二分查

River Hopscotch-[二分查找、贪心]

Description Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at th

二分查找方法

问题描述: 二分查找指定的int数组 问题分析: 时间复杂度为O(logN) 代码实现: package c02; /**  * @project: DataStructureAndAlgorithmAnalysis  * @filename: BinarySearch  * @version: 0.10  * @author: Jimmy Han  * @date: 22:57 2015/7/7  * @comment: Test Purpose  * @result:  */ public 

二分查找

递归版(在区间[x, y)中找v的位置) 1 //递归版二分查找 2 int bsearch(int * A, int x, int y, int v) 3 { 4 5 if(v<a[x] || v>a[y-1]) return -1; 6 int m = x + (y-x)/2; //此处能不能用int m = (x+y)/2,需要仔细考虑(暂时想不到原因) 7 if(A[m]==v) return m; 8 else if(A[m]>v) return bsearch(A, x, m

二分查找JAVA实现

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表.重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功. 一.概念 二分查

rwkj 1430 二分查找

#include<iostream>using namespace std;int n,k,a[10000]; int binsearch(int low,int high){ int i,len,s;while(low<high) { len=(high+low)/2; for(s=0,i=0;i<n;i++) s+=a[i]/len; if(s>k) low=len+1; else if(s<k) high=len-1; else return len; }}int

uva:10487 - Closest Sums(二分查找)

题目:10487 - Closest Sums 题目大意:给出一组数据,再给出m个查询的数字.要求找到这组数据里的两个数据相加的和最靠近这个查询的数据,输出那两个数据的和. 解题思路:二分查找,这样找到的话,就输出查询的数值,但是要注意找不到的情况:这里最靠近的值不一定是在找不到的时刻的前一次数据,所以要维护最靠近的要查询数的数值. 代码: #include <stdio.h> #include <algorithm> #include <stdlib.h> using

php二分查找

<?php /** * 二分查找:查找一个值在数组中的位置 *@$val:查找的值 *@$arr:操作的数组,前提是按顺序排列 */ header("content-type:text/html;charset = utf-8"); function biary_search($arr,$val){ $num = count($arr); $low = 0; $high = $num - 1; while($low<$high){ $mid = floor(($high-$

二分查找算法的 JavaScript 实现

二分查找在查找[指定值]在[有序]数据中的[位置]时是一种高效的算法. 以下仅提供 ES5 版本. var arr = [0, 2, 4, 27, 28, 54, 67, 74, 75, 79, 86, 97, 289, 290, 678] function binarySearch(arr, val) { var start = 0, end = arr.length - 1; while (start <= end) { var mid = Math.floor((start + end)