Rumah > pembangunan bahagian belakang > tutorial php > PHP实现二分查找算法(代码详解)

PHP实现二分查找算法(代码详解)

藏色散人
Lepaskan: 2023-04-06 13:16:01
ke hadapan
8188 orang telah melayarinya

二分查找又称折半查找,二分查找算法要求数据必须是有序的,以下是php实现二分查找算法的代码。

一:递归方式

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

$array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89];

$target = 73;

$low = 0;

$high = count($array)-1;

function bin_search($array, $low, $high, $target){

    if ( $low <= $high){

        var_dump($low, $high);echo "\n";

        $mid intval(($low+$high)/2 );

        if ($array[$mid] ==  $target){

            return true;

        }elseif ( $target < $array[$mid]){

            return  bin_search($array, $low$mid-1, $target);

        }else{

            return  bin_search($array, $mid+ 1, $high, $target);

        }

    }

    return false;

}

$find = bin_search($array, $low, $high, $target);

var_dump($find);

Salin selepas log masuk

执行结果

1

2

3

4

5

6

7

8

9

int(0)

int(25)

int(13)

int(25)

int(20)

int(25)

int(20)

int(21)

bool(true)

Salin selepas log masuk
Salin selepas log masuk

我们看到,经过4次二分查找,查找区间不断折半,最终找到了$target。

二:循环方式

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

$array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89];

$target = 73;

function bin_search($array, $target)

{

    $low = 0;

    $high = count($array)-1;

    $find = false;

    while (true){

        if ($low <= $high){

            var_dump($low, $high);echo "\n";

            $mid = intval(($low + $high)/2);

            if ($array[$mid] == $target){

                $find = true;

                break;

            } elseif ($array[$mid] < $target){

                $low = $mid+1;

            } elseif ($array[$mid] > $target){

                $high = $mid-1;

            }

        } else {

            break;

        }

    }

    return $find;

}

$find = bin_search($array, $target);

var_dump($find);

Salin selepas log masuk

执行结果

1

2

3

4

5

6

7

8

9

int(0)

int(25)

int(13)

int(25)

int(20)

int(25)

int(20)

int(21)

bool(true)

Salin selepas log masuk
Salin selepas log masuk

我们看到,两种方式过程和结果相同。下面我们来测试下针对关联数组的二分查找算法:

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

$array = [&#39;a&#39;=>1,&#39;b&#39;=>3,&#39;c&#39;=>6,&#39;d&#39;=>9,&#39;e&#39;=>13,&#39;f&#39;=>18,&#39;g&#39;=>19,&#39;h&#39;=>29,&#39;i&#39;=>38];

$target = 19;

function bin_search($array, $target)

{

    $low = 0;

    $high = count($array)-1;

    $key_map = array_keys($array);

    $find = false;

    while (true){

        if ($low <= $high){

            var_dump($low, $high);echo "\n";

            $mid = intval(($low + $high)/2);

            if ($array[$key_map[$mid]] == $target){

                $find = true;

                break;

            } elseif ($array[$key_map[$mid]] < $target){

                $low = $mid+1;

            } elseif ($array[$key_map[$mid]] > $target){

                $high = $mid-1;

            }

        } else {

            break;

        }

    }

    return $find;

}

$find = bin_search($array, $target);

var_dump($find);

执行结果

int(0)

int(8)

int(5)

int(8)

bool(true)

Salin selepas log masuk

两次二分查找,找到了$target,针对关联数组,我们使用了php的array_keys函数获得这个关联有序数组的key,通过key间接比对$target和$array的值。

Atas ialah kandungan terperinci PHP实现二分查找算法(代码详解). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Label berkaitan:
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan