的地得的用法,算法-二分查找,风寒感冒

频道:我们的头条 日期: 浏览:148

算法-二分查找

Try to have wisdom worthy of your wealth,not only money.
尽力去具有配得上你财富的才智,而非只要金钱。

什么是二分查找?

二分查找也称减半查找(Binary Search),它是一种功率较高的查找办法。可是,减半查找要求线性表有必要选用次序存储结构,并且表中元素按关键字有序摆放。
能够发现,二分查找的两个条件:

  1. 次序结构,由于每个处理单元要依据巨细判别放弃一半

  2. 按关键字摆放,由于要依据关键字比较

完成的思路呢?

引证PHP算法之二分查找 - 个人文章 - SegmentFault 思否的描绘:其实,二分查找也仍是比较简单了解的,大约便是一分为二,然后两头比较,保存有用区间,持续一分为二查找,直到找到或许超出区间则完毕,所以二分查找的根本过程是:

  1. 确定要查找的区间

  2. 确定要二分时的参照点

  3. 区间内选取二分点

  4. 依据二分点的值,归纳左右区间状况以及求解的意图,舍去一半无用的区间

  5. 持续在有用区间重复上面的过程

代码完成

递归

  1. /**

  2. * 循环完成二分查找

  3. * @param $arr 待查找区间

  4. * @param $num 目标值

  5. * @return int 回来找到的键

  6. */

  7. function binary_search($arr, $num)

  8. {

  9. if (!is_array($arr) || empty($arr)) {

  10. return -1;

  11. }


  12. $count = count($arr);

  13. $lower = 0;

  14. $higher = $count - 1;


  15. // 最低点比最高点大就退出

  16. // tip: 鸿沟判别条件时怎么理清思路?

  17. // 1.最简单想到的进入循环的条件是"左右点不重合($lower < higher)"

  18. // 2."重合"的状况是"个例",使用反向思想,假如不包含的话,是否导致成果犯错。

  19. // 这里是会漏掉数组只要一个值并且这个值等于$num的状况的,所以应当包含等于

  20. while ($lower <= $higher)

  21. {

  22. $middle = intval(($lower + $higher) / 2);

  23. if ($arr[$middle] > $num) {

  24. // 查找数比参照点小,舍去右边

  25. $higher = $middle - 1;

  26. } elseif ($num > $arr[$middle]) {

  27. // 查找数比参照点大,舍去左面

  28. $lower = $middle + 1;

  29. } else {

  30. // 查找数与参照点持平,则找到回来

  31. return $middle;

  32. }

  33. }


  34. // 未找到,回来-1

  35. return -1;

  36. }

非递归

  1. /**

  2. * 递归法二分查找

  3. * @param $arr 待查找的规模

  4. * @param $num 查找值

  5. * @param $lower 下限

  6. * @param $high 上限

  7. * @return int 回来找到的键

  8. */

  9. function binary_search_recursion(&$arr, $num, $lower, $high)

  10. {

  11. if (!is_array($arr) || empty($arr) || $lower > $high) {

  12. return -1;

  13. }


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


  15. if ($arr[$middle] > $num) {

  16. // 查找数比参照点大,舍去左面持续查找

  17. return binary_search_recursion($arr, $num, $lower, $middle - 1);

  18. } elseif ($arr[$middle] < $num) {

  19. // 查找数比参照点小,舍去右边持续查找

  20. return binary_search_recursion($arr, $num, $middle + 1, $high);

  21. } else {

  22. return $middle;

  23. }

  24. }

成果

  1. $arr = [1,2,3,5,6,7,8,9];

  2. echo binary_search($arr, 9); // 3

  3. echo PHP_EOL;

  4. echo binary_search_recursion($arr, 9, 0, count($arr) - 1); // 3

时空复杂度

在有序数组中假如用暴力的算法去查找,也便是逐一遍历比较,那么时刻复杂度是O(n);可是,用二分查找后,由于每次能够舍去一半查找区间,所以会将时刻复杂度削减到O(logn),算法更优。

C言语完成

  1. #include <stdio.h>

  2. int binary_search(const int arr[], int num, int lower, int higher) {

  3. while (lower <= higher) {

  4. int mid = (lower + higher) / 2;

  5. if (arr[mid] > num) {

  6. higher = mid - 1;

  7. } else if (arr[mid] < num) {

  8. lower = mid + 1;

  9. } else {

  10. return mid;

  11. }

  12. }

  13. return -1;

  14. }

  15. int binary_search_recursion(int arr[], int num, int lower, int higher) {

  16. int mid = (lower + higher) / 2;

  17. if (arr[mid] > num) {

  18. return binary_search_recursion(arr, num, lower, mid - 1);

  19. } else if (arr[mid] < num) {

  20. return binary_search_recursion(arr, num, mid + 1, higher);

  21. } else {

  22. return mid;

  23. }

  24. }

  25. int main() {

  26. int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

  27. int pos = binary_search_recursion(arr, 5, 0, 8); //4

  28. int pos2 = binary_search(arr, 5, 0, 8);

  29. printf("%d\n", pos);

  30. printf("%d\n", pos2);

  31. }

参阅

PHP算法之二分查找 - 个人文章 - SegmentFault 思否

热门
最新
推荐
标签