算法
在数学和计算机科学之中，算法是一个被定义好的、计算机可施行之指示的有限步骤或次序，常用于计算、数据处理和自动推理。作为一个有效方法，算法被用于计算函数，它包含了一系列定义清晰的指令，并可于有限的时间及空间内清楚的表述出来。
第一天(二分查找)
二分查找
二分查找的主要思路十分简单,通过两个指针(或下标,或其他类似的东西)比较中间值来达到快速排除的效果,前提左到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;
}
第一个错误的版本
这道题正确版本就是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;
}
搜索插入位置
这个数组是有序的及符合我们二分需要的逻辑,但是者共我们有两种可能, 及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;
}
