Question note 4 (the first wrong version, search the insertion position)

---

subject

First wrong version
Search insert location

One 、 Topic 1

1. Code

// 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. other

1） The condition for finding the first error is that the minimum value is equal to the maximum value .
2） Intermediate value is wrong , The intermediate value may be the first wrong , So assign it to the new maximum ; But if the intermediate value is not wrong , Then the new minimum value is the intermediate value plus 1.

Two 、 Topic two

1. Code

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. other

The difference between the above two methods lies in the positioning of numbers in non array , In the first solution ,min The left side of the must be smaller than target,max The right side of must be larger than target.