# Exercises II

## Search Insert Position

原题链接：<https://leetcode.com/problems/search-insert-position/>

难度： easy

参考解法：

```cpp
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int i=0,site=0;
        while(i<nums.size()){
            if(nums[i]<target) site++;
            i++;
        }
        return site;
    }
};
```

Binary Search

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

## First Bad Version

原题链接：<https://leetcode.com/problems/first-bad-version/>

难度：easy

参考解答：

Linear search 超时

```cpp
class Solution {
public:
    int firstBadVersion(int n) {
        int i=0;
        while(i<n){
            if(isBadVersion(i)) break;
            i++;
        }
        return i;
    }
};
```

Binary search Accepted

```cpp
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{min=mid+1;}
        }
        return min;
    }
};
```

## Find First and Last Position of Element in Sorted Array

原题链接：<https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/>

难度：medium

参考解答：

```cpp
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
    int idx1 = lower_bound(nums, target);
    int idx2 = lower_bound(nums, target+1)-1;
    if (idx1 < nums.size() && nums[idx1] == target)
        return {idx1, idx2};
    else
        return {-1, -1};
    }
    
    int lower_bound(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while (l <= r) {
            int mid = (r-l)/2+l;
            if (nums[mid] < target)
                l = mid+1;
            else
                r = mid-1;
        }
        return l;
    }
};
```

## Sum of Mutated Array Closest to Target

原题链接：<https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/>

难度：medium

题意分析：给定一个数组arr和一个整数target。

给出一个数值value，使其满足在arr中比value大的值改成value之后，arr中数的总和最接近target。

这个value可以是不是数组中的数。

> Input: arr = \[4,9,3], target = 10&#x20;
>
> Output: 3&#x20;
>
> Explanation: When using 3 arr converts to \[3, 3, 3] which sums 9 and that's the optimal answer.
>
> Input: arr = \[2,3,5], target = 10&#x20;
>
> Output: 5
>
> Input: arr = \[60864,25176,27249,21296,20204], target = 56803&#x20;
>
> Output: 11361

提示：ternary search/binary search

[参考解法](https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/discuss/463306/JavaC%2B%2BPython-Just-Sort-O\(nlogn\))：

```cpp
class Solution {
public:
    int findBestValue(vector<int>& A, int target) {
        sort(A.begin(), A.end());
        int n = A.size(), i = 0;
        while (i < n && target > A[i] * (n - i))
            target -= A[i++];
        return i == n ? A[n - 1] : int(round((target - 0.0001) / (n - i)));
    }
};
```

[Round函数](http://cplusplus.com/reference/cmath/round/?kw=round)

> Returns the integral value that is nearest to x, with halfway cases rounded away from zero.

[Binary Search解法](https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/discuss/463268/C%2B%2B-16ms-binary-search-short-readable-code)：

```cpp
class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
        int l, r, mi, s=0, m=-1;
        for(int v:arr) s += v, m=max(m,v);
        
        if(s<=target) return m; // return the max value since we will keep all nums as is

        for(l=1,r=m;l<r;) {
            mi=(l+r)/2;
            s=0;
            for(int v:arr) s += (v>mi)?mi:v;
            if(s>=target) r=mi;
            else          l=mi+1;
        }
        // check if we are 1 step off the target 
        int s1=0,s2=0;
        for(int v:arr) s1 += (v>l)?(l):v, s2 += (v>l-1)?(l-1):v;
        
        return (abs(s2-target) <= abs(s1-target)) ? l-1 : l;
    }
};
```

## Find Minimum in Rotated Sorted Array

原题链接：<https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/>

难度：medium

参考解法：

```cpp
class Solution {
public:
    int findMin(vector<int>& nums) {
        int res=INT_MAX;
        for(int n:nums) res=min(n,res);
        return res;
    }
};
```

## Find Minimum in Rotated Sorted Array II

原题链接：<https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/>

难度：hard

参考解法：

```cpp
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://celia-qian.gitbook.io/leetcode-notebook-2020-2021/linear-list/array/exercises-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.