对数器用于在自己的本地平台验证算法正确性，用于算法调试，无需online judge。
好处：
实现原理:
代码实现:
#include <algorithm>
using namespace std;
void Swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
void insertSort(vector<int> &v)
{
for (int i = 0; i < v.size() - 1; i++)
{
int end=i;
while (end >= 0)
{
if (v[end + 1] < v[end])
{
Swap(v[end + 1], v[end]);
end--;
}
else
{
break;
}
}
}
}
void print(vector<int> &v)
{
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test1()
{
//vector<int> v = {6, 5, 4, 3, 2, 1};
vector<int> v = {6, 6, 9, 10, 2,2, 1};
insertSort(v);
print(v);
}
//准备一个随机数组（样本）生成器
//函数名：generateRandomVector
//函数功能描述：随机数组（样本）生成器
//函数参数： size 生成数组最大尺寸
// value 数组每个元素的最大值
//返回值： vector<int> 生成的数组
//for test
vector<int> generateRandomVector(int size, int value)
{
//time 函数返回从 1970 年 1 月 1 日午夜开始到现在逝去的秒数，因此每次运行程序时，它都将提供不同的种子值。
srand((int)time(NULL));//为随机数生成器产生随机种子
//分配随机大小的数组，产生随机数的范围公式number = (rand()%(maxValue - minValue +1)) + minValue;
vector<int> result(rand() % (size + 1));
for (auto i = 0; i < result.size(); i++)
{
result[i] = rand() % (value + 1);
}
return result;
}
//大样本测试
//函数名：main
//函数功能描述：大样本测试
//函数参数： size 生成数组最大尺寸
// value 数组每个元素的最大值
//返回值： vector<int> 生成的数组
//for test
int main()
{
auto test_time = 50000;//测试次数，设置比较大，排除特殊情况
auto size = 10;//生成数组最大尺寸
auto value = 30;//生成数组每个元素的最大值
auto if_accept = true;//方法是否正确标志位
for(auto i = 0; i < test_time; i++)
{
//拷贝初始化，生成新的数组向量
vector<int> nums(generateRandomVector(size, value));
//生成两个临时数组拷贝
vector<int> nums1(nums);
vector<int> nums2(nums);
//绝对正确方法
sort(nums1.begin(), nums1.end());
//自己写的方法，想要测试的算法
insertSort(nums2);
//判断两个向量是否相同，vector类已经重载了比较运算符，不用自己实现，不相同说明算法不正确
if(nums1 != nums2)
{
if_accept = false;
//输出结果不相等的原始向量
for(auto c: nums)
{
cout << c << " ";
}
break;
}
}
//输出结果
cout << (if_accept ? "nice!\n" : "false!\n");
}
代码实现:
bool binarySearch(vector<int>& v , int targer)
{
if(v.empty())return false;
int L=0;
int R=v.size()-1;
int mid=0;
// while(L<=R)// 以 L和R之间至少一个数,二分的逻辑就不一样了
while(L<R) // 以L和R之间至少两个数, 最后一次需要判断一下L的位置,已经验证过了,边界条件就是这样.
{
mid=L + (R-L>>1);
if(v[mid] == targer)
{
return true;
}
else if(v[mid] > targer)
{
R = mid - 1;
}
else
{
L = mid + 1;
}
}
return v[L] == targer; // 最后一次没有判断, 两种情况 L==R , R == L-1 -- R已经判断了,所以两种情况都是需要判断L的,有点难理解这个边界条件;
}
边界控制:
解题步骤：
代码一：
int nearestIndexR1(vector<int>& v,int targer)
{
int L=0;
int R=v.size()-1;
int index=-1;
while(L<=R)
{
int mid = L + ((R-L)>>1);
if(v[mid]<=targer)
{
index=mid;
L=mid+1;
}
else
{
R = mid -1;
}
}
return index;
}
代码二：
int nearestIndexR2(vector<int>& v,int targer)
{
int L=0;
int R=v.size()-1;
int index=-1;
while(L<R)
{
int mid = L + ((R-L)>>1);
if(v[mid]<=targer)
{
index=mid;
L=mid+1;
}
else
{
R = mid -1;
}
}
if(v[L]<=targer)index=L;
return index;
}
解题步骤：
int nearestIndexL(vector<int>& v,int targer)
{
int L=0;
int R=v.size()-1;
int index=-1;
while(L<=R)
{
int mid= L + ((R-L)>>1);
if(v[mid]>=targer)
{
index = mid ;
R = mid -1 ;
}
else
{
L = mid +1;
}
}
return index;
}
在一个无序数组中, 值有可能正, 负, 或者零, 数组中任由两个相邻的数一定不相等.
定义局部最小:
1.长度为1，arr[0]就是局部最小；
2.数组的开头，如果arr[0] < arr[1] ，arr[0]被定义为局部最小。
3.数组的结尾，如果arr[N-1] < arr[N-2] ，arr[N-1]被定义为局部最小。
任何一个中间位置i, 即数组下标1~N-2之间, 必须满足arr[i-1] < arr[i] <arr[i+1] ,叫找到一个局部最小。
请找到任意一个局部最小并返回。
需要注意：
解题步骤：
任意两个都相邻是不相等的，所以中间必有存在一个变化曲线, 但是为什么先往下降，最后是上扬
中间我不管你怎么连这个变化曲线一定存在局部最小
如图：
四种情况
int getLessIndex(vector<int>& nums)
{
if(nums.empty())return -1;
if(1<nums.size() && nums[0]<nums[1])return 0;
if(nums[nums.size()-2]<nums[nums.size()-1])return nums.size()-1;
int left = 1;
int right = nums.size()-2;
int mid=0;
while(left<right)
{
mid=left+ (right-left>>1);
if(nums[mid]>nums[mid+1])
{
left = mid +1 ;
}
else if (nums[mid]>nums[mid-1])
{
right = mid -1;
}
else{
return mid;
}
}
if(nums[left]nums[left+1] && nums[left]< nums[left-1]) return left;
return -1;
}
void testgetLessIndex()
{
vector<int> v = {5,4,3,2,1,10,9};
cout<< v[getLessIndex(v)]<<endl;
}
int main()
{
testgetLessIndex();
}