ホームページ > バックエンド開発 > PHPチュートリアル > PHP半探索アルゴリズム事例の詳細説明

PHP半探索アルゴリズム事例の詳細説明

php中世界最好的语言
リリース: 2023-03-26 18:48:02
オリジナル
1874 人が閲覧しました

今回は、PHP 半検索アルゴリズムの事例について詳しく説明します。PHP 半検索を使用する際の 注意事項 は何ですか?実際の事例を見てみましょう。

概要:

二分探索テクノロジー、ハーフサーチとも呼ばれます。その前提として、線形テーブル内のレコードはキーの順序 (通常は小さいものから大きいものへの順序) である必要があり、線形テーブルは順番に格納される必要があります。

基本的な考え方:

順序付きリストでは、指定された値が中央のレコードのキーと等しい場合、検索は成功します。指定された値が中央のレコードのキーより大きい場合は、中央のレコードの左半分で検索を続けます。指定された値が中央のレコードのキーより大きい場合は、中央のレコードの右半分で検索を続けます。検索が成功するか、すべての検索領域にレコードがなく検索が失敗するまで、上記のプロセスを繰り返します。

コード:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

<?php

//二分搜索(折半查找)算法(前提是数组必须是有序数组) 时间复杂度是 O(logn)

$i = 0; //存储对比的次数

//@param 待查找数组

//@param 待搜索的数字

function binsearch($arr,$num){

 $count = count($arr);

 $lower = 0;

 $high = $count - 1;

 global $i;

 while($lower <= $high){

  $i ++; //计数器

  if($arr[$lower] == $num){

   return $lower;

  }

  if($arr[$high] == $num){

   return $high;

  }

  $middle = intval(($lower + $high) / 2);

  if($num < $arr[$middle]){

   $high = $middle - 1;

  }else if($num $arr[$middle]){

   $lower $middle + 1;

  }else{

   return $middle;

  }

 }

 //返回-1表示查找失败

 return -1;

}

$arr array(0,1,16,24,35,47,59,62,73,88,99);

$pos = binsearch($arr,62);

print($pos);

echo "<br>";

echo $i;

ログイン後にコピー
実行結果:

1

2

7

3

ログイン後にコピー

概要:

二分探索の時間計算量は

O(logn)です。しかし、二分探索では順序付きテーブル(配列)を順次格納することが前提となるため、順序付きテーブルに対して頻繁に挿入や削除操作が必要な場合、順序付きソートの維持には多大な負荷がかかります。

この記事の事例を読んだ後は、この方法を習得したと思います。さらに興味深い情報については、php 中国語 Web サイトの他の関連記事に注目してください。

推奨読書:

PHP 長時間接続のユースケース分析

PHP アプリケーションのコンテナ化とデプロイメントの使用方法の詳細な説明

以上がPHP半探索アルゴリズム事例の詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

関連ラベル:
ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
PHP 拡張子 intl
から 1970-01-01 08:00:00
0
0
0
phpのデータ取得?
から 1970-01-01 08:00:00
0
0
0
PHP GET エラー レポート
から 1970-01-01 08:00:00
0
0
0
phpを上手に学ぶ方法
から 1970-01-01 08:00:00
0
0
0
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート