做题笔记4（第一个错误的版本，搜索插入位置）

---

题目

第一个错误的版本
搜索插入位置

一、题目一

1.代码

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
    
public:
    int firstBadVersion(int n) {
    
        int min=1;
        int max=n;
        while(min<=max)
        {
    
            int mid=min+(max-min)/2;
            if(isBadVersion(mid))
            {
    
                max=mid;
            }
            else if(isBadVersion(mid)==0)
            {
    
                min=mid+1;
            }
            if(min==max)
            {
    
                return min;
            }
        }
        return min;
    }
};

2.其他

1）找出第一个错误的条件是最小值与最大值相等。
2）中间值为错误，中间值有可能为第一个错误的，故将其赋值给新的最大值；但若中间值不为错误的，则新的最小值为该中间值加1。

二、题目二

1.代码

class Solution {
    
public:
	int searchInsert(vector<int>& nums, int target) {
    
		int n = nums.size();
		int min = 0;
		int max = n - 1;
		while (min <= max)
		{
    
			int mid = min + (max - min) / 2;
			if (nums[mid] < target)
			{
    
				min = mid + 1;
			}
			else if (nums[mid] >= target)
			{
    
				max = mid - 1;
			}
		}

		return min;
	}
};

class Solution {
    
public:
	int searchInsert(vector<int>& nums, int target) {
    
		int n = nums.size();
		int min = 0;
		int max = n-1;
		int an = 0;
		int b = 0;
		while (min <= max)
		{
    
			int mid = min + (max - min) / 2;
			if (nums[mid] < target)
			{
    
				min = mid + 1;
			}
			else if (nums[mid] > target)
			{
    
				max = mid - 1;
			}
			else if (nums[mid] == target)
			{
    
				an = mid;
				b = 1;
				break;
			}
		}
        if(b==0)
        {
    
            an=min;
        }
		return an;
	}
};

2.其他

上述两种方法的区别在于对非数组中的数的定位，第一种解决方案中，min的左边一定小于target，max的右边一定大于target。