T1
题
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。
你必须编写一个具有 O(log n) 时间复杂度的算法。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
- 你可以假设
nums中的所有元素是不重复的。 n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
最终答案
int search(int* nums, int numsSize, int target) {
int i=0;
while (nums[i]<target&&i<numsSize-1) i++;
if(nums[i]==target) return i;
else return -1;
}
int search(int* nums, int numsSize, int target) {
int i=0;
while (nums[i]<target&&i<numsSize-1) i++;
if(nums[i]==target) return i;
else return -1;
}
思路
非常自然地想到从头开始将数组的每一个元素与target对比，相等时返回下标
历程
- 看漏了不存在返回下标的情况导致过不了相应的样例
- 没有看到已经给出的numsSize（数组的长度）试图通过*nums[i+1]！=NULL 来判断i有没有越界可惜至少C语言中数组末尾元素的下一个指针未必是NULL，并且长度不大于i的话nums[i+1]这种写法直接就错了
- 经典忘记了数组从0开始，纯用脑想没有理清判断条件的表达式到底该怎么写，几乎放弃思考不过就-1这样弄出来了......(丑陋)
总结
- 这个故事告诉我们要认真读题先确认好要考虑的情况，并且明确有哪些已知的东西
- C语言中如果位置数组长度需要用函数来获取
- （静态） int len = sizeof(arr)/sizeof(arr[0])
- arr为数组名
- sizeof（）得到占用的字节数，除以单个元素占用的字节数及得元素个数
反转！
经过D老师的提醒此处复杂度为O(n)而没到题目要求的O(log n)，拙劣的笔者因为对不清楚复杂度并且自己不熟二分查找而忽略了题目的提示
- 由于确实不熟又已经看过D老师的代码，这里只总结学到的东西）
- int型的除法只保留整数（天呐虽然是在复健但没想到这个都忘了）
- （来自D老师）
// 假设 left = 2,000,000,000, right = 2,000,000,000
int mid = (left + right) / 2;
// left + right = 4,000,000,000 超过了 int 的范围（21亿多）
// 💥 溢出！结果是负数或错误值// 安全的写法：
int mid = left + (right - left) / 2;
// right - left = 0, 不会溢出
真·最终答案
（仍然来自D老师）
int search(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) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;
}
真·总结
- 感到（重新？）学习编程任重道远，现在娱乐大家，争取以后启发大家
- 考虑到这里的二分查找需要已知数据是顺序排列的，在这个时候使用二分查找显然比线性查找更优，但是对于位置顺序的序列考虑到排序所需的复杂度其实线性查找复杂度更低
- 对算法的理解还是需要从实践中产生，笔者已经严肃反思过去眼不高手低的作风，至少弄清楚基础的东西（）