[binary search simple question] leetcode 35. search insertion position, 69. Square root of X, 367. Effective complete square, 441. Arrange coins

LeetCode 35. Search insert location

https://leetcode.cn/problems/search-insert-position/
Given a sort array and a target value , Find the target value in the array , And return its index . If the target value does not exist in the array , Return to where it will be inserted in sequence .

nums by No repeating elements Of Ascending Arrange arrays

Please use a time complexity of O(log n) The algorithm of .

Example 1:
Input : nums = [1,3,5,6], target = 5
Output : 2

Example 2:
Input : nums = [1,3,5,6], target = 2
Output : 1

Example 3:
Input : nums = [1,3,5,6], target = 7
Output : 4

Solution

int searchInsert(int* a, int n, int target){
    
    int l = 0, r = n - 1;
    int ans = n;
    int mid;
    while (l <= r) {
    
        mid = (l + r) / 2;
        if (a[mid] >= target) {
    
            ans = mid;
            r = mid - 1;
        } else {
    
            l = mid + 1;
        }
    }
    return ans;
}

LeetCode 69. x The square root of

https://leetcode.cn/problems/sqrtx
Give you a nonnegative integer x , Calculate and return x Of Arithmetical square root .
Because the return type is an integer , The result is only the integral part , The decimal part will be removed .
Request can't be used sqrt(x) and pow(x, 0.5).

Example 1：
Input ：x = 4
Output ：2

Example 2：
Input ：x = 8
Output ：2
explain ：8 The arithmetic square root of is 2.82842..., Because the return type is an integer , The decimal part will be removed .

Solution

int mySqrt(int x){
    
    long long l = 0, r = x, mid, ans;
    while (l <= r) {
    
        mid = (l + r) / 2;
        if (mid * mid <= x) {
    
            ans = mid;
            l = mid + 1;
        } else {
    
            r = mid - 1;
        }
    }
    return ans;
}

LeetCode 367. Effective complete square number

https://leetcode.cn/problems/valid-perfect-square
Given a Positive integer num , Write a function , If num It's a complete square , Then return to true , Otherwise return to false .
Advanced ： Don't Use any built-in library functions , Such as sqrt .

Example 1：
Input ：num = 16
Output ：true

Example 2：
Input ：num = 14
Output ：false

Solution

bool isPerfectSquare(int num){
    
    long long l = 0, r = num, mid, temp; 
    while (l <= r) {
    
        mid = (l + r) / 2;
        temp = mid * mid;
        //  Add one more judgment condition 
        if (temp == num) {
    
            return true;
        } else if (temp < num) {
    
            l = mid + 1;
        } else {
    
            r = mid - 1;
        }
    }
    return false;
}

Another more convenient way ： Directly in 69 Based on the question, you can directly make a judgment on the return value

bool isPerfectSquare(int num){
    
    long long l = 0, r = num, mid, ans; 
    while (l <= r) {
    
        mid = (l + r) / 2;
        if (mid * mid <= num) {
    
	        ans = mid;
            l = mid + 1;
        } else {
    
            r = mid - 1;
        }
    }
    return ans * ans == num;
}

LeetCode 441. Arrange coins

https://leetcode.cn/problems/arranging-coins
You have a total of n Coin , And plan to arrange them in a ladder . For a by k A ladder of rows , Its first i OK, there must be exactly i Coin . The last line of the ladder Probably It's incomplete .

Here's a number n , Calculate and return to form Full ladder row The total number of rows of .

Input ：n = 5
Output ：2
explain ： Because the third line is incomplete , So back 2 .

Input ：n = 8
Output ：3
explain ： Because the fourth line is incomplete , So back 3 .

Solution

Violence law ：

int arrangeCoins(int n){
    
    int i;
    for (i = 1; n >= i; i++) {
    
        n -= i;
    }
    return i - 1;
}

Dichotomy ：
In fact, it's two points i The process of
whole i Layer or whole i Layer plus extra incomplete next layer , The results are ans = i
The meet i * (i + 1) / 2 <= n < i * (i + 1) / 2 + (i + 1), Get ans = i

int arrangeCoins(int n){
    
    long long ans = 0, l = 1, r = n, mid;
    while (l <= r) {
    
        mid = (l + r) / 2;
        if (mid * (mid + 1) / 2 <= n) {
    
            ans = mid;
            l = mid + 1;
        } else {
    
            r = mid - 1;
        }
    }
    return ans;
}

Mathematical method ：
To assume that n It can be arranged completely x A staircase , namely $\frac{x(x+1)}{2}=n$
Into a quadratic equation of one variable ：$x^2+x-2n=0$
solve equations ：$x_1=\frac{-1+\sqrt{8n+1}}{2},x_2=\frac{-1-\sqrt{8n+1}}{2}$
because $x_2<0$ disqualification , So take $\lfloor x_1\rfloor$ For the solution .

int arrangeCoins(int n){
    
    return (int) ((sqrt(8 * (long long)n + 1) - 1) / 2);
}