アルゴリズム-ペアルックアップ(二分割ルックアップ)C++実装
これは基本的な検索アルゴリズムです.数を読み込むだけで(N)の時間量が必要になりますので、このような問題を言う時は全部仮読み込みとしています.
アルゴリズムの一般的な時間で問題を一部(約1/2)に縮小すると、このアルゴリズムはO(logn)レベルであると考えます.
まず対点検索の時間複雑度はO(logn)です.
すでに撮影済みの数列が前提です.
アルゴリズムの一般的な時間で問題を一部(約1/2)に縮小すると、このアルゴリズムはO(logn)レベルであると考えます.
まず対点検索の時間複雑度はO(logn)です.
すでに撮影済みの数列が前提です.
//
// main.cpp
// binarySearch
//
// Created by Alps on 14-7-24.
// Copyright (c) 2014 chen. All rights reserved.
//
#include <iostream>
int binarySearch(const int A[], int X, int N){
int start = 0, end = 0, mid;
end = N;
while (start <= end) {
mid = (start + end)/2;
if (X > A[mid]) {
start = mid+1;
continue;
}else if (X < A[mid]){
end = mid-1;
continue;
}else{
return mid;
}
}
return -1;
}
int main(int argc, const char * argv[])
{
int A[]={1 ,4 , 6, 8, 19, 34, 93};
int N = sizeof(A)/sizeof(int);
int X = 19;
int locate = binarySearch(A, X, N);
if (locate == -1) {
printf("Can't find the element %d
",X);
}else{
printf("The element %d is locate in %d
",X,locate);
}
return 0;
}
この中には原理がありません.問題は簡単です