template
<
typename Find_Array,
typename Found_Num,
typename How_Long
>
inline unsigned long long find
(
Find_Array *arr,
Found_Num num,
How_Long length
)
{
unsigned long long left = 0, right = length - 1;
if(arr[0] == num) {
return 0;
}
if(arr[right] == num) {
return right;
}
while (right - left > 1) {
unsigned long long mid = (left + right) / 2;
if(arr[mid] > num) {
right = mid;
}
else if(arr[mid] < num) {
left = mid;
}
else {
return mid;
}
}
return length;
}
template
<
typename Find_Array,
typename Found_Num
>
inline unsigned long long find
(
std::vector <Find_Array> &arr,
Found_Num num
)
{
unsigned long long left = 0, right = arr.size() - 1;
if(arr[0] == num) {
return 0;
}
if(arr[right] == num) {
return right;
}
while (right - left > 1) {
unsigned long long mid = (left + right) / 2;
if(arr[mid] > num) {
right = mid;
}
else if(arr[mid] < num) {
left = mid;
}
else {
return mid;
}
}
return arr.size();
}
解释:
1.重复定义两次同名函数的意义是使查找函数既支持普通数组又支持动态数组(给一个函数套两个模版)
2.代码while循环条件是left - right > 1的原因是防止有傻逼查找数组内没有的数(用时间换安全度)至于为什么是left - right > 1我就不必多说了
3.传入的数组必须有序 不然能不能找到就随缘了
4.代码并不具备使找到的数是数组中最前项的功能 具体实现我待会发评论区
5.对于普通数组 查找时输入数组名 查找数字 数组元素个数
6.对于动态数组 查找时输入数组名 数组元素个数就行了
7.返回一律是下标
8.while循环前加两个if是因为实际查找范围是1～最大下标-1(while内并没有针对left和right进行判断) 因此0和最大下标需要特判
9.如果元素未找到 返回最大下标+1(数组元素个数)
2 comments
-
陈锦润 LV 8 @ 2024-11-16 21:16:05最新版(无需排序也能查找 只是比较慢)
template < typename Find_Array, typename Found_Num, typename How_Long > inline unsigned long long find ( Find_Array *arr, Found_Num num, How_Long length ) { unsigned long long left = 0, right = length - 1; if(arr[0] == num) { return 0; } if(arr[right] == num) { return right; } while (right - left > 1) { unsigned long long mid = (left + right) / 2; if(arr[mid] > num) { right = mid; } else if(arr[mid] < num) { left = mid; } else { right = mid; while(right - left > 1) { mid = (left + right) / 2; if(arr[mid] == num) { right = mid; } else { left = mid; } } return right; } } for ( int l = 0, r = length - 1, lm = length / 2 - 1, rm = length / 2; r > rm; ++l, --lm, --r, ++rm ) { if(arr[l] == num) { return l; } if(arr[r] == num) { return r; } if(arr[lm] == num) { return lm; } if(arr[rm] == num) { return rm; } } return length; } #include <vector> template < typename Find_Array, typename Found_Num > inline unsigned long long find ( std::vector <Find_Array> &arr, Found_Num num ) { unsigned long long left = 0, right = arr.size() - 1; if(arr[0] == num) { return 0; } if(arr[right] == num) { return right; } while (right - left > 1) { unsigned long long mid = (left + right) / 2; if(arr[mid] > num) { right = mid; } else if(arr[mid] < num) { left = mid; } else { right = mid; while(right - left > 1) { mid = (left + right) / 2; if(arr[mid] == num) { right = mid; } else { left = mid; } } return right; } } for ( int l = 0, r = arr.size() - 1, lm = arr.size() / 2 - 1, rm = arr.size() / 2; r > rm; ++l, --lm, --r, ++rm ) { if(arr[l] == num) { return l; } if(arr[r] == num) { return r; } if(arr[lm] == num) { return lm; } if(arr[rm] == num) { return rm; } } return arr.size(); }-
@ 2024-11-16 21:43:43
其实我没有算过for循环直接遍历查找时是用几个变量遍历期望的时间复杂度才最低 但是我觉得用4个变量很酷而且好写 所以我就写4个了
-
-
@ 2024-11-13 21:45:40
已实现
template < typename Find_Array, typename Found_Num, typename How_Long > inline unsigned long long find ( Find_Array *arr, Found_Num num, How_Long length ) { unsigned long long left = 0, right = length - 1; if(arr[0] == num) { return 0; } if(arr[right] == num) { return right; } while (right - left > 1) { unsigned long long mid = (left + right) / 2; if(arr[mid] > num) { right = mid; } else if(arr[mid] < num) { left = mid; } else { right = mid; while(right - left > 1) { mid = (left + right) / 2; if(arr[mid] == num) { right = mid; } else { left = mid; } } return right; } } return length; } template < typename Find_Array, typename Found_Num > inline unsigned long long find ( std::vector <Find_Array> &arr, Found_Num num ) { unsigned long long left = 0, right = arr.size() - 1; if(arr[0] == num) { return 0; } if(arr[right] == num) { return right; } while (right - left > 1) { unsigned long long mid = (left + right) / 2; if(arr[mid] > num) { right = mid; } else if(arr[mid] < num) { left = mid; } else { right = mid; while(right - left > 1) { mid = (left + right) / 2; if(arr[mid] == num) { right = mid; } else { left = mid; } } return right; } } return arr.size(); }
- 1