Binary Search Learning (2)

Click to view the code

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

Give you a non-negative integer x, calculate and return the arithmetic square root of X.

Since the return type is an integer, only the integer part of the result is retained, and the decimal part is discarded.

Note: No built-in exponential functions and operators, such as pow(x, 0.5) or x ** 0.5, are allowed.

Click to view the code

class Solution {
public:
    int mySqrt(int x) {
if(x==0)
{
    return 0;
}
if(x==1)
{
    return 1;
}
int left=0,right=x-1;
while(left<=right)
{
    int mid=left+(right-left)/2;
    if((long long)mid*mid==x)
    {
return mid;
    }
    else if((long long)mid*mid<x)
    {left=mid+1;}
    else if((long long)mid*mid>x)
    {
        right=mid-1;
    }

}
    return left-1;
    }
};

The rules for guessing a number game are as follows:

For each round of the game, I randomly choose a number from 1 to n. Please guess which number was selected.
If you make a mistake, I'll tell you if your guess is larger or smaller than the one I selected.
You can get a guess by calling a predefined interface, int guess(int num), and the return value has three possible scenarios (-1, 1, or 0):

-1: I chose a number smaller than what you guessed < num
1: I chose a number larger than your guess pick > num
0: I chose the same number as you guessed. Congratulations! Bingo! pick == num
Return the number I selected.

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

int guessNumber(int n)
{
	int right=n;
    int left=0; 
        while (left <= right) { // Cycle until the left and right endpoints of the interval are the same
            int mid = left + (right - left) / 2; // Prevent calculation overflow
            if (guess(mid) < 0) {
                right = mid-1; // The answer is in [left, mid]
            } else if(guess(mid)>0){
                left = mid + 1; // The answer is in the interval [mid+1, right]
            }else if(guess(mid)==0)
            {return mid;}
        }
        // There is left == right, and the interval is reduced to a point, which is the answer.
        return left-1;
        }

 

return right;

 

The integer array nums is arranged in ascending order, and the values in the array are different from each other.

Nums rotates an array to [nums[k], nums[k+1],..., nums[n-1], nums[0], nums[1],..., nums[1],..., nums[k-1] (subscripts count from 0) before passing it to the function. For example, [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2] after being rotated at subscript 3.

Give you a rotated array of nums and an integer target, which returns its subscript if the target exists in nums, or -1 if it does not.

 

Click to view the code

int search(int* nums, int numsSize, int target){
int left=0,right=numsSize-1;
while(left<=right)
{
    int mid=left+(right-left)/2;
    if(nums[mid]==target)
    return mid;
    else if(nums[mid]>=nums[left])//=To add here
    {
        if(target>=nums[left]&&target<=nums[mid])
        {
            right=mid-1;
        }
        else{left=mid+1;}
    }
    else if(nums[mid]<nums[left])
    { if(target>=nums[mid]&&target<=nums[right])
        {
            left=mid+1;
        }
        else{right=mid-1;}}
}
return -1;
}

otherwise

Select left because/to omit the part after the decimal point

An array with a known length of n is pre-sorted in ascending order and rotated 1 to N times to obtain an input array. For example, the original array nums = [0,1,2,4,5,6,7] may get after changing:
If you rotate it four times, you get [4,5,6,7,0,1,2]
If you rotate it seven times, you get [0,1,2,4,5,6,7]
Notice that the result of one rotation of the array [a[0], a[1], a[2],..., a[n-1]] is the array [a[n-1], a[0], a[1], a[2],..., a[n-2].

You are given an array of nums elements with different values, which was originally an ascending array and rotated several times as described above. Please find and return the smallest element in the array.

int findMin(int* nums, int numsSize){
int left=0,right=numsSize;
while(left<right)
{
    int mid=left+(right-left)/2;
    if(nums[mid]<=nums[numsSize-1])
    {
        right=mid;
    }
    else
    {
        left=mid+1;
    }

}
return nums[left];
  
}