第二周作业-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;
   }
   return -1;
}

int main() {
int nums[] = {-1,0,3,5,9,12};
int target;
int numsSize = sizeof(nums) / sizeof(nums[0]);
scanf("%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));
*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/

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

没有力扣账号的请注册力扣账号
务必把二分法框架背住!注意区分区间!左闭右闭还是左闭右开.然后自己上网搜索一下二分法变型!