[C言語]リニアナビゲーション&バイナリナビゲーションの実現

ナビゲーションアルゴリズムはいくつかあります.
関数を使用して、線形検索とバイナリ検索を実現します.
1)リニアナビゲーション
LinearSearchは、シーケンスナビゲーションとも呼ばれる線形ナビゲーションで、その名の通り、直線上で値を検索します.LinearSearch関数を実装し,それを可能にする.
リニアナビゲーションアルゴリズムの実装

#include <stdio.h>

LinearSearch(int *a, int len, int val) {

	for(int i=0; i<len; i++)
    	if(a[i]==val) return i
 
    return -1;
}

この関数は、データセットaとそのデータ数lenと、検索する値valとを受け入れる.
そしてaの0番目のデータから1番目の2番目の...最後に、valであるか否かを判定するために、データ値を順次巡回する.valが正常に見つかった場合は、その位置を返します.
そうでない場合は、-1を返します.
時間の複雑さ
線形ナビゲーションアルゴリズムの時間複雑度はO(N)であった.
最悪の場合、検索する値がナビゲーション方向の最後にあるか、データセットが存在しません.
この場合、データセットのすべての要素はO(N)にナビゲートする必要があります.
2)バイナリナビゲーション
バイナリナビゲーション(BinarySearchと呼ばれる)は、単純にはパイロット値である.
これはよくバックハンドゲームをするときに使う探索方法です.BinarySearch関数を実装しましょう.
バイナリナビゲーションアルゴリズム実装

#include <stdio.h>

BinarySearch(int *a, int len, int val) {

    int first = 0;
    int last = len-1;
    int mid;
    
    while( first <= last ) {
    
    	mid = (first+last)/2;
        
    	if(a[mid] == val) {
			return mid;
		}
		else {
			if(a[mid] > val)
				last = mid - 1;
			else
				first = mid + 1;	
		}
        
    }
    
    return -1;
}

バイナリ・ナビゲーションは、ナビゲーションする範囲を含まない場合に値を検索するナビゲーション・アルゴリズムであってもよい.

first:有効なナビゲーションデータ範囲の開始点

last:有効ナビゲーションデータ範囲の末尾

mid:現在ナビゲート中のデータ位置(最初の+最後の)/2

まずmidをfirstとlastの間の中間値に調整します.a[mid]==valが真偽であると判別する.
正しい場合は、現在のインデックス位置(mid)を返します.
もしそうでなければ.
1.a[mid] > val-lastをmid-1に調整します.
2.a[mid] < val -firstをmid+1に調整します.
これは、前述したリニアナビゲーションと比較して、高速ナビゲーション方法かもしれませんが、データが整列しなければならないことを前提としています.
時間の複雑さ

バイナリ探索アルゴリズムの時間的複雑さはO(log N)であった.
私たちは半分に分けて探求するからです.
最悪の場合はlog N時間かかります.
3)線形探索VSバイナリ探索
では、線形検索とバイナリ検索では、どの検索アルゴリズムが良いのでしょうか.
検索する値が最初の場所にある場合は、
リニアナビゲーションでは、すぐに見つけることができるかもしれません.
逆に,バイナリ探索の場合,log Nの時間が必要である.
逆に、検索する値が真ん中のmidにある場合.
バイナリナビゲーションならすぐに見つかるはずです.
線形探索にはN/2の時間が必要である.
実際には、より良いアルゴリズムはなく、状況によって異なるだけです.
与えられた状況に応じてより効率的なアルゴリズムを選択してください.