二分法-526互联

本周练习内容
题目来自于力扣(掌握二分法)
题目链接

https://leetcode.cn/problems/binary-search/

代码如下
#include <stdio.h>

int search(int* nums, int numsSize, int target) {
int left = 0;
   int right = numsSize - 1;

 while (left <= right) {//左闭右闭，合法的区间
int mid = left + (right - left) / 2;
if (nums[mid] == target)	return mid;
else if (nums[mid] < target)	left = mid + 1;
else right = mid - 1;
}
 /*  int right=numsSize;
 while (left < right) {//左闭右开，合法的区间
 int mid= left + (right - left) / 2;
 if (nums[mid] == target)	return mid;
 else if (nums[mid] < target)	left = mid + 1;
 else right = mid ;
 }*/

return -1;
}

int main() {
int nums[] = { -1,0,3,5,9,12 };
int target;
int numsSize = sizeof(nums) / sizeof(nums[0]);
scanf_s("%d", &target);
int result = search(nums, numsSize, target);

if (result != -1) {
printf("%d\n", result);
}
else {
printf("-1\n");
}

return 0;
}

https://leetcode.cn/problems/search-insert-position/

自己写的

int search(int* nums, int numsSize, int target) {
   int left=0;
   int right=numsSize-1;
   
   while(left<=right){
int mid=left+(right-left)/2;
   	if(nums[mid]==target)	return mid;
   	else if(nums[mid]<target)	left=mid+1;
   	else right=mid-1;
   }
   
   for(int i=0;i<numsSize+1;i++){
   	if(target<nums[i]){
   		return i;
   		break;
	   }
   }
   
   return numsSize;
}

官方解法

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

最简写法

int searchInsert(int* nums, int numsSize, int target) {
for (int i=0;i<numsSize;i++){
if (nums[i]>=target)
return i;
}
return numsSize;
}

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

官方题解

int searchBoundary(int* nums, int numsSize, int target, bool   isLeft){
int left = 0, right = numsSize - 1, ans = numsSize;

while (left <= right) {

    int mid = (left + right) / 2;
    if (nums[mid] > target || (isLeft && nums[mid] >= target)) {
//取左区间：找右边界的时候nums[mid] > target需要抛弃，找左边界的时候nums[mid] >= target需要抛弃
    right = mid - 1;
    ans = mid;//右边界：最右一个大于target的位置；左边界：最左一个等于target的位置；
    } else 
		{ 
//取右区间：找右边界的时候nums[mid] <= target需要抛弃，找左边界的时候nums[mid] < target需要抛弃
    left = mid + 1;
    }

}

return ans;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    int * ret = malloc(sizeof(int) * 2);
    memset(ret, -1, sizeof(ret));//设置内存块的函数，ptr 是指向要设置的内存的指针，value 是要设置的值，num 是要设置的字节数
   
	 *returnSize = 2;
    int l = searchBoundary(nums, numsSize, target, true), r = searchBoundary(nums, numsSize, target, false) - 1;

    if(l != numsSize && nums[l] == target)//返回边界值有效
    ret[0] = l, ret[1] = r;
    return ret;
}

最快解法

int findleftbound(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){
    left=mid+1;
    }else if(nums[mid]>target){
    right=mid-1;
    }else{
    right=mid-1;
    }
}
if(left<0 || left>=numsSize){
return -1;
}

return nums[left]==target?left:-1;
}

int findrightbound(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){
    left=mid+1;
    }else if(nums[mid]>target){
    right=mid-1;
    }else{
    left=mid+1;
    }
}
if(right<0 || right>=numsSize){
return -1;
}
return nums[right]==target?right:-1;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
int* res=(int*)malloc(sizeof(int)*2);

int left=0,right=numsSize-1;
int mid=left+(right-left)/2;

res[0]=findleftbound(nums,numsSize,target);
res[1]=findrightbound(nums,numsSize,target);
*returnSize=2;
return res;
}

https://leetcode.cn/problems/sqrtx/

也是用到了二分查找的思想

int mySqrt(int x) {
int l = 0, r = x, ans = -1;

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

return ans;
}

https://leetcode.cn/problems/valid-perfect-square/

妙解：4=1+3 9=1+3+5 16=1+3+5+7以此类推，模仿它可以使用一个while循环，不断减去一个从1开始不断增大的奇数，若最终减成了0，说明是完全平方数，否则，不是。

bool isPerfectSquare(int num) 
{
int num1 = 1;
	while(num > 0) 
    {
	 num -= num1;
	 num1 += 2;
    }
	return num == 0;
}

基于二分查找

bool isPerfectSquare(int num) {
int left = 0, right = num;
while (left <= right) {
    int mid = (right - left) / 2 + left;
    long square = (long) mid * mid;
    if (square < num) {
    left = mid + 1;
    } else if (square > num) {
    right = mid - 1;
    } else {
    return true;
    }
}
    return false;
}

务必把二分法框架背住!注意区分区间!左闭右闭还是左闭右开.然后自己上网搜索一下二分法变型!