【leetcode系列】小菜鸡的leetcode第10题:第一个错误的版本

依旧二分法查找的演化。

思路是类似于神经网络的激活函数。

当位于该点之前，全部为False（0），位于该点之后，全部为True（1），改点时，有且仅有该点，左边相邻为False，右边相邻为True

#解法1：遍历最少，储存最少
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        low,high=1,n
        #if n==1 or n==2:
        #    return 1
        #else:
        while(low<=high):
            mid = low+((high-low)//2)
            if isBadVersion(mid)==False and isBadVersion(mid-1)==False:
                low=mid+1
            elif isBadVersion(mid)==True and isBadVersion(mid-1)==True:
                high=mid-1
            else: 
                #isBadVersion(mid-1)=='false' and isBadVersion(mid+1)=='true':
                return mid

解法一结果：

#解法2：常规解法，思路同“查找插入位置”，大于该指针位置的都为ture，小于该指针位置的都为false
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        low,high=1,n
        while(low 
解法二结果：
 
 
官方解法，指针遍历后，基于边界的判断（java版本，思路相同）
public class Solution {

    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        // 特殊判断
        if (nums[len - 1] < target) {
            return len;
        }

        // 程序走到这里一定有 nums[len - 1] >= target，插入位置在区间 [0..len - 1]
        int left = 0;
        int right = len - 1;
        // 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target){
                // 下一轮搜索的区间是 [mid + 1..right]
                left = mid + 1;
            } else {
                // 下一轮搜索的区间是 [left..mid]
                right = mid;
            }
        }
        return left;
    }
}