查看: 1733|回复: 0

[PHP代码] 常见查找算法之php, js,python版

发表于 2018-1-3 08:00:00
常用算法 >>>1. 顺序查找, 也叫线性查找, 它从第一个记录开始, 挨个进行对比, 是最基本的查找技术 javaScript 版顺序查找算法:
  1. 1 // 顺序查找(线性查找) 只做找到即返回
  2. 2
  3. 3 // javaScript 版
  4. 4
  5. 5 function search(data,needle)
  6. 6
  7. 7 {
  8. 8
  9. 9 for(var i=0;i<data.length;i++)
  10. 10
  11. 11 {
  12. 12
  13. 13 if(data[i] == needle && typeof data[i] == typeof needle)
  14. 14
  15. 15 {
  16. 16
  17. 17 return i;
  18. 18
  19. 19 }
  20. 20
  21. 21 }
  22. 22
  23. 23 return false;
  24. 24
  25. 25 }
  26. 26
  27. 27
  28. 28 var data = [100,10,2,7,8,6];
  29. 29
  30. 30 console.log(search(data,7));// 3
  31. 31
  32. 32 console.log(search(data,'7'));// false
复制代码
php版顺序查找算法:
  1. 1 <?php
  2. 2
  3. 3 // php版
  4. 4
  5. 5 function search($data,$needle)
  6. 6
  7. 7 {
  8. 8
  9. 9 $data_len = count($data);
  10. 10
  11. 11 for($i=0;$i<$data_len;$i++)
  12. 12
  13. 13 {
  14. 14
  15. 15 if($data[$i] === $needle) return $i;
  16. 16
  17. 17 }
  18. 18
  19. 19 return false;
  20. 20
  21. 21 }
  22. 22
  23. 23
  24. 24
  25. 25 $data = [100,10,2,7,8,6];
  26. 26
  27. 27 var_dump(search($data,7));// int(3)
  28. 28
  29. 29 var_dump(search($data,'7'));// bool(false)
复制代码
python3 版顺序查找算法:
  1. 1 # python3 版本
  2. 2
  3. 3 def search(data,needle) :
  4. 4
  5. 5 dataLen = len(data)
  6. 6
  7. 7 for i in range(dataLen) :
  8. 8
  9. 9 if data[i] == needle and type(data[i]) == type(needle) : return i
  10. 10
  11. 11 return False
  12. 12
  13. 13
  14. 14 data = [100,10,2,7,8,6]
  15. 15
  16. 16 print(search(data,7)) # 3
  17. 17
  18. 18 print(search(data,'7')) # False
  19. 19
  20. 20 print(search(data,6)) # 5
复制代码
>>>二分找查, 折半查找

核心思想:

1. 用low , high , middle 表示待查找区间的 下界, 上界,中间 的坐标

2. 取中间位置 middle = floor((low+high)/2)

3. 用给定值与 中间位置的值 作比较

等于: 查找成功

大于: 待查数据在区间的后半段 设low 为 middle+1

小于: 待查数据在区间的前半段 设high 为 middle-1

4.数据是排序好的

5.直到越界 (low>high) 查找失败, 结束

PHP版二分查找算法:
  1. 1 <?php
  2. 2
  3. 3 // 二分法 折半查找 PHP版
  4. 4
  5. 5 $data_list = [1,2,4,5,5,6,10,12];
  6. 6
  7. 7 function bisearch($data_list,$needle)
  8. 8
  9. 9 {
  10. 10
  11. 11 $low = 0;
  12. 12
  13. 13 $high = count($data_list)-1;
  14. 14
  15. 15 if($data_list[$low] == $needle) return $low;
  16. 16
  17. 17 if($data_list[$high] == $needle) return $high;
  18. 18
  19. 19 while($high>=$low)
  20. 20
  21. 21 {
  22. 22
  23. 23 $middle = floor(($low+$high)/2);
  24. 24
  25. 25 if($needle == $data_list[$middle])
  26. 26
  27. 27 {
  28. 28
  29. 29 return $middle;
  30. 30
  31. 31 }elseif($needle>$data_list[$middle])
  32. 32
  33. 33 {
  34. 34
  35. 35 $low = $middle+1;
  36. 36
  37. 37 }else{
  38. 38
  39. 39 $high = $middle-1;
  40. 40
  41. 41 }
  42. 42
  43. 43 }
  44. 44
  45. 45 return false;
  46. 46
  47. 47 }
  48. 48
  49. 49
  50. 50
  51. 51 print_r(bisearch($data_list,10)); // 6
  52. 52
  53. 53 print_r(bisearch($data_list,5)); // 3
  54. 54
  55. 55 print_r(bisearch($data_list,13)); // false
复制代码
python 3版 二分查找算法:
  1. 1 import math
  2. 2
  3. 3 # python3 版二分查找算法
  4. 4
  5. 5 def bisearch(data_list,needle) :
  6. 6
  7. 7 low,high = 0,len(data_list)-1
  8. 8
  9. 9 if needle == data_list[low] : return low
  10. 10
  11. 11 if needle == data_list[high] : return high
  12. 12
  13. 13 while high>=low :
  14. 14
  15. 15 middle = math.floor((high+low)/2)
  16. 16
  17. 17 if needle == data_list[middle] : return middle
  18. 18
  19. 19 elif needle > data_list[middle] : low = middle+1
  20. 20
  21. 21 else : high = middle-1
  22. 22
  23. 23 return False
  24. 24
  25. 25
  26. 26
  27. 27 data_list = [1,2,4,5,5,6,10,12]
  28. 28
  29. 29 print(bisearch(data_list,10)); # 6
  30. 30
  31. 31 print(bisearch(data_list,5)); # 3
  32. 32
  33. 33 print(bisearch(data_list,13)); # False
复制代码
javaScript 版二分查找算法:
  1. 1 // js 版二分查找
  2. 2
  3. 3 function bisearch(data_list,needle)
  4. 4
  5. 5 {
  6. 6
  7. 7 var low = 0,high = data_list.length-1
  8. 8
  9. 9 if (needle == data_list[low] ) return low
  10. 10
  11. 11 if (needle == data_list[high]) return high
  12. 12
  13. 13 while (high>=low)
  14. 14
  15. 15 {
  16. 16
  17. 17 var middle = Math.floor((low+high)/2)
  18. 18
  19. 19 if(needle == data_list[middle])
  20. 20
  21. 21 {
  22. 22
  23. 23 return middle
  24. 24
  25. 25 }else if(needle>data_list[middle])
  26. 26
  27. 27 {
  28. 28
  29. 29 low = middle + 1
  30. 30
  31. 31 }else{
  32. 32
  33. 33 high = middle - 1
  34. 34
  35. 35 }
  36. 36
  37. 37 }
  38. 38
  39. 39 return false
  40. 40
  41. 41 }
  42. 42
  43. 43 data_list = [1,2,4,5,5,6,10,12]
  44. 44
  45. 45 console.log(bisearch(data_list,10)); // 6
  46. 46
  47. 47 console.log(bisearch(data_list,5)); // 3
  48. 48
  49. 49 console.log(bisearch(data_list,13)); // False
复制代码

>>> 插值查找 (由二分查找改进)

二分查找的公式:

middle = (low+high)/2 => low+(1/2)*(high-low)

插值查找的公式由上面演变, 主要改进的是二分之一部分:

middle = low+((needle-data[low])/(data[high]-data[low]))*(high-low)

对二分查找跟插值查找的一个说明:

插值查找对于公布均匀的数据, 速度比二分查找快(插值查找次数少),例如对下面这类数据

$data = [1,2,3,6,7,9,10,11,...]

对于分布不均匀的数据, 二分查找要比插值查找快 例如下:

$data = [4,100,300,685,3452,...]

PHP版 插值查找算法:
  1. 1 <?php
  2. 2
  3. 3 // 二分查找优化(插值查找) PHP版
  4. 4
  5. 5 $data_list = [1,2,4,5,5,6,10,12];
  6. 6
  7. 7 function interpolation($data_list,$needle)
  8. 8
  9. 9 {
  10. 10
  11. 11 $low = 0;
  12. 12
  13. 13 $high = count($data_list)-1;
  14. 14
  15. 15 if($data_list[$low] == $needle) return $low;
  16. 16
  17. 17 if($data_list[$high] == $needle) return $high;
  18. 18
  19. 19 while($high>=$low)
  20. 20
  21. 21 {
  22. 22
  23. 23 $middle = floor($low+(($needle-$data_list[$low])/($data_list[$high]-$data_list[$low]))*($high-$low));
  24. 24
  25. 25 if($needle == $data_list[$middle])
  26. 26
  27. 27 {
  28. 28
  29. 29 return $middle;
  30. 30
  31. 31 }elseif($needle>$data_list[$middle])
  32. 32
  33. 33 {
  34. 34
  35. 35 $low = $middle+1;
  36. 36
  37. 37 }else{
  38. 38
  39. 39 $high = $middle-1;
  40. 40
  41. 41 }
  42. 42
  43. 43 }
  44. 44
  45. 45 return false;
  46. 46
  47. 47 }
  48. 48
  49. 49
  50. 50
  51. 51 print(interpolation($data_list,10)); // 6
  52. 52
  53. 53 print(interpolation($data_list,5)); // 3
  54. 54
  55. 55 print(interpolation($data_list,13)); // false
  56. 56
  57. 57
  58. 58
  59. 59 $index = interpolation($data_list,10);
  60. 60
  61. 61 echo $data_list[$index];// 10
  62. 62
  63. 63
  64. 64 /*
  65. 65
  66. 66 注: 1.floor 返回的是浮点数 如 6 类型为float
  67. 67
  68. 68 2.false 用print,echo 输出是空字符串
  69. 69
  70. 70 */
复制代码
python3版 插值查找算法:
  1. 1 import math
  2. 2
  3. 3 # python3 插值查找算法
  4. 4
  5. 5 def interpolation(data_list,needle) :
  6. 6
  7. 7 low,high = 0,len(data_list)-1
  8. 8
  9. 9 if needle == data_list[low] : return low
  10. 10
  11. 11 if needle == data_list[high] : return high
  12. 12
  13. 13 while high>=low :
  14. 14
  15. 15 middle = math.floor(
  16. 16
  17. 17 low+
  18. 18
  19. 19 ((needle-data_list[low])/(data_list[high]-data_list[low]))*
  20. 20
  21. 21 (high-low)
  22. 22
  23. 23 )
  24. 24
  25. 25 if needle == data_list[middle] : return middle
  26. 26
  27. 27 elif needle > data_list[middle] : low = middle+1
  28. 28
  29. 29 else : high = middle-1
  30. 30
  31. 31 return False
  32. 32
  33. 33
  34. 34
  35. 35 data_list = [1,2,4,5,5,6,10,12]
  36. 36
  37. 37 print(interpolation(data_list,10)); # 6
  38. 38
  39. 39 print(interpolation(data_list,5)); # 3
  40. 40
  41. 41 print(interpolation(data_list,13)); # False
复制代码
js 版插值查找算法:
  1. 1 // js版 插值查找算法
  2. 2
  3. 3 function interpolation(data_list,needle)
  4. 4
  5. 5 {
  6. 6
  7. 7 var low = 0,high = data_list.length-1
  8. 8
  9. 9 if (needle == data_list[low] ) return low
  10. 10
  11. 11 if (needle == data_list[high]) return high
  12. 12
  13. 13 while (high>=low)
  14. 14
  15. 15 {
  16. 16
  17. 17 var middle = Math.floor(
  18. 18
  19. 19 low+((needle-data_list[low])/(data_list[high]-data_list[low]))*
  20. 20
  21. 21 (high-low)
  22. 22
  23. 23 )
  24. 24
  25. 25 if(needle == data_list[middle])
  26. 26
  27. 27 {
  28. 28
  29. 29 return middle
  30. 30
  31. 31 }else if(needle>data_list[middle])
  32. 32
  33. 33 {
  34. 34
  35. 35 low = middle + 1
  36. 36
  37. 37 }else{
  38. 38
  39. 39 high = middle - 1
  40. 40
  41. 41 }
  42. 42
  43. 43 }
  44. 44
  45. 45 return false
  46. 46
  47. 47 }
  48. 48
  49. 49 data_list = [1,2,4,5,5,6,10,12]
  50. 50
  51. 51 console.log(interpolation(data_list,10)); // 6
  52. 52
  53. 53 console.log(interpolation(data_list,5)); // 3
  54. 54
  55. 55 console.log(interpolation(data_list,13)); // False
复制代码

小结:

以上有php,python,js 版常见的查找算法:

1. 顺序(线性) 查找

2. 二分查找 (折半查找)

3. 插值查找 (二分查找优化 适用于分布均匀的数据)

4. 前提是数据排好序, 顺序



回复

使用道具 举报