算法
在数学和计算机科学之中,算法是一个被定义好的、计算机可施行之指示的有限步骤或次序,常用于计算、数据处理和自动推理。作为一个有效方法,算法被用于计算函数,它包含了一系列定义清晰的指令,并可于有限的时间及空间内清楚的表述出来。
第一天(二分查找)
二分查找
704. 二分查找 - 力扣(LeetCode)
二分查找的主要思路十分简单,通过两个指针(或下标,或其他类似的东西)比较中间值来达到快速排除的效果,前提左到mid和mid到右的部分都各自有着特点可以快速排查.
int search(int* nums, int numsSize, int target) { int left = 0; int right = numsSize - 1; int mid = (left + right) / 2; while (left <= right)//随题目要求改变 { mid = (right + left) / 2; if (nums[mid] > target) { right = mid - 1;//这个是要随着题目要求所改变的 } else if (nums[mid] < target) { left = mid + 1;//这个是要随着题目要求所改变的 } else if (nums[mid] == target) { return mid; } } return -1; }
第一个错误的版本
278. 第一个错误的版本 - 力扣(LeetCode)
这道题正确版本就是true错误版本就是false我们就要找到true和flase的交换点
类似如: 0 0 0 0 0 0 1 1 1 1 1 1 1要找到第一个零即可.
这道就符合二分的思想,两段数据left到mid和mid到right之间都是有着类似的特点所以我们可以使用二分思想,只需根据思路更改三部分即可.
int firstBadVersion(int n) { int left = 0; unsigned int right = n; int mid = (left+right)/2; while(left < right)//left = right的时候就是找到了 { mid = (left + right) / 2; if(isBadVersion(mid) == false) { left = mid + 1;//我们要找第一个true及1所以为mid为0的时候直接将mid跳过. } else { right = mid; } } return right; }
搜索插入位置
35. 搜索插入位置 - 力扣(LeetCode)
这个数组是有序的及符合我们二分需要的逻辑,但是者共我们有两种可能, 及target存在和不存在,当target存在时,我们的 else if(nums[mid]==target)就可将它返回
当target不存在时当我们left和right值相同时结束循环返回left或right都可
int searchInsert(int* nums, int numsSize, int target) { int left = 0; int right = numsSize - 1; if(target >nums[right]) return numsSize; if(target < nums[left]) return 0; int mid = (left+right) / 2; while(left < right) { mid = (left+right) / 2; if(nums[mid] < target) left = mid+1; else if(nums[mid]>target) right = mid; else if(nums[mid]==target) return mid; } return right; }