如何在1000万个整数中快速查某个整数？——⼆分查
时间复杂度O(logn)，很强
适⽤于数组的数据结构，但不适⽤于链表，因为链表不⽀持随机访问
只能查有序数组，如果是⽆序的，需要进⾏⼀次排序（最低时间复杂度O(nlogn)）
数据量⼩不适⽤，直接⽤遍历查即可
数据量太⼤也不适⽤，因为数据结构是数组，需要的是连续的内存空间
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include "TreeNode.h"
#include "ListNode.h"
using namespace std;
// ⼆分查具有O(logn)的时间复杂度，很强，但是只能⽤于数组的数据结构，像链表就不适合
cstring转为int// ⼆分查⾮递归法
int binarySearch(int num[], int length, int key){
if(length < 1)
return -1;
int low = 0;
int high = length - 1;
int middle = 0;
while(low <= high){
// 以后尽量使⽤位运算，不直接⽤(low + high) / 2是为了防⽌加法溢出
middle = low + ((high - low) >> 1);
if(num[middle] == key)
return middle;
if(num[middle] > key)
high = middle - 1;
else if(num[middle] < key)
low = middle + 1;
}
// 没到则返回-1
return -1;
}
// ⼆分查递归⽅法
int binarySearchPlus(int num[], int low, int high, int key){
if(low > high)
return -1;
int middle = low + ((high - low) >> 1);
if(num[middle] == key)
return middle;
if(num[middle] > key)
return binarySearchPlus(num, low, middle - 1, key);
else
return binarySearchPlus(num, middle + 1, high, key);
}
int main(int argc, char* argv[]){
int arr[8] = {8,7,6,5,4,3,2,1};
cout<<binarySearch(arr, 8, 5)<<endl;
cout<<binarySearchPlus(arr, 0, 7, 5)<<endl;
return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。