目录

• —、第一题
• • 1. 原题链接
  • 2. 解题思路
  • 3. 代码
• 二、第二题
• • 1. 原题链接
  • 2. 解题思路
  • 3. 代码
• 三、第三题
• • 1. 原题链接
  • 2. 解题思路
  • 3. 代码
• 四、第四题
• • 1. 原题链接
  • 2. 解题思路
  • 3. 代码
• 五、星球推荐

        坚持每一天！！！
        在最简单的形式中，二分查找对具有指定左索引和右索引的连续序列进行操作。这就是所谓的查找空间。二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。

—、第一题

1. 原题链接

        原题链接：35. 搜索插入位置

        给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

        请必须使用时间复杂度为 O(log n) 的算法。

2. 解题思路

        二分查找，用ans存储下标，mid中间下标，使用left和right对数组进行折半查找，nums[mid] >= target或nums[mid] < target进行折半判断在那一半。循环得出结果。

3. 代码

int searchInsert(int* nums, int numsSize, int target){   int left = 0, right = numsSize - 1;   int mid = 0;   int ans = numsSize;   while(left <= right){mid = (left + right) >> 1;if(nums[mid] >= target){    ans = mid;    right = mid-1;} else left = mid+1;   }   return ans;}

二、第二题

1. 原题链接

        原题链接：704. 二分查找

        给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

2. 解题思路

        二分查找，通过nums[mid] > target或nums[mid] < target查找target在那一半区域，多次循环至查找到结果。

3. 代码

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

三、第三题

1. 原题链接

        原题链接：剑指 Offer 53 - I. 在排序数组中查找数字 I

        统计一个数字在排序数组中出现的次数。

2. 解题思路

        因为时有序数组，查找到target与target+1两值的下标，用target+1下标减去target下标既得到target出现的次数。

3. 代码

int searchtar(int* nums, int numsSize, int target){   int left = 0, right = numsSize - 1;   int mid = 0;   int ans = numsSize;   while(left <= right){mid = (left + right) >> 1;if(nums[mid] >= target){    ans = mid;    right = mid-1;} else left = mid+1;   }   return ans;}int search(int* nums, int numsSize, int target){   int ret = searchtar(nums, numsSize, target);   if(ret == numsSize || nums[ret] != target)return 0;   return searchtar(nums, numsSize, target+1) - ret;}

四、第四题

1. 原题链接

        原题链接：911. 在线选举

        给你两个整数数组 persons 和 times 。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。

        对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。

        在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。

        实现 TopVotedCandidate 类：

        TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。
        int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。

2. 解题思路

        先对示例分析
        第一行["TopVotedCandidate","q","q","q","q","q","q"]是操作，
        第二行[[[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]],[3],[12],[25],[15],[24],[8]]参数。
        即先调用TopVotedCandidate初始化，参数persons times分别为[0,1,1,0,0,1,0], [0,5,10,15,20,25,30]
        再调用了6次q的方法进行进行查询，6次参数t分别为[3],[12],[25],[15],[24],[8]
        persons, times 之间一一对应，在times[i]的时候，编号为persons[i]的这个人票数加一。
        当前票数最多的人即领先， 查询是返回时间为t时，领先的人的编号persons[i]。

        在times规定下，times[i]时刻对领先人进行处理，得到tops[]，然后使用二分查找，找出在t时刻之前保持的领先人是谁。

3. 代码

typedef struct {   int * tops;   int * times;   int timesSize;} TopVotedCandidate;TopVotedCandidate* topVotedCandidateCreate(int* persons, int personsSize, int* times, int timesSize) {   if (NULL == persons || NULL == times || persons <= 0 || timesSize <= 0) {return NULL;   }   TopVotedCandidate * obj = (TopVotedCandidate *)malloc(sizeof(TopVotedCandidate));   int * voteCounts = (int *)malloc(sizeof(int) * personsSize);    memset(voteCounts, 0 ,sizeof(int) * personsSize);   obj->timesSize = timesSize;   obj->tops = (int *)malloc(sizeof(int) * personsSize);   obj->times = (int *)malloc(sizeof(int) * timesSize);   int top = -1;   for (int i = 0; i < personsSize; ++i) {++voteCounts[persons[i]];if (top < 0 || voteCounts[persons[i]] >= voteCounts[top]) {    top = persons[i];}obj->tops[i] = top; // 领先人obj->times[i] = times[i];   }   free(voteCounts);   return obj;}int topVotedCandidateQ(TopVotedCandidate* obj, int t) {   int ans;   int left = 0, right = obj->timesSize - 1;   while (left <= right) {int mid = (left + right) >> 1;if (obj->times[mid] <= t) {    ans = mid;    left = mid + 1;} else right = mid - 1;   }   return obj->tops[ans];}void topVotedCandidateFree(TopVotedCandidate* obj) {   free(obj->tops);   free(obj->times);   free(obj);}

五、星球推荐

        星球链接：英雄算法联盟

星球里有什么?
        【朋友圈】一个极致精准的自律、编程、算法的小圈子。
        【算法集训】以月为单位组织算法集训，每天四题，风雨无阻。
        【排行榜】每天、每周都会有榜单，激励大家不断进步，不断成长。
        【个人规划】每个人都写好自己的规划，也可以查看他人的规划，时刻警醒自己不掉队。
        【打卡挑战】每日一题打卡、每日早起打卡、算法集训打卡、规划完成情况打卡。
在星球里做什么?
        目前星球人数达到360+，在星球里你能够遇到一群志同道合之人，因为都是花钱进来的，你不会看到任何浑水摸鱼的人，每个人都有自己的每月规划，星主每月都会组织算法集训，每天一起刷题，你可以看到别人的解题报告，取其之长，补己之短。