我有一個我需要做的測驗評估。有一個問題一直困擾著我。
我有一個數字陣列，我需要找到一種方法來在陣列中找到那個數字，我已經部分完成了。問題出現在專案的下一步中，即它必須容納一百萬件物品。
我相信這是二分搜索。如何進行二分搜索或等效搜索？
#include <iostream>
#include <sys/resource.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <algorithm>
#include <vector>
using namespace std;
class Answer
{
public:
static bool exists(int ints[], int size, int k)
{
for(int i=0; i<size; i ){
if(ints[i]<k){
return true;
}
}
return false;
}
};
下面的圖片給出了我需要什么和我的代碼的想法
我需要的：
uj5u.com熱心網友回復：
為什么不直接使用標準庫函式？
static bool exists(int ints[], int size, int k)
{
return std::binary_search(ints, ints size, k);
}
uj5u.com熱心網友回復：
我已經看到你得到了答案，但是自己實作二分搜索從來都不是壞事，尤其是在演算法課程中，所以它可能會幫助你理解演算法：
static bool exists(const int ints[], int size, int k) {
int left = 0, right = size-1;
while(right-left>1) {
int middle = (right left)/2;
if(ints[middle] > k) right = middle;
else left = middle;
}
if(ints[right] == k || ints[left] == k) return true;
return false;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/351763.html