`
purpen
  • 浏览: 796842 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

PHP算法:折半查找法(又称二分查找法)

阅读更多

二分查找又称折半查找 ,它是一种效率较高的查找方法。


【二分查找要求】:

1.必须采用顺序存储结构

2.必须按关键字大小有序排列。


【优缺点】折半查找法的优点是比较次数少,查找速度快,平均性能好;

  其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而 查找频繁的有序列表。


【算法思想】首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记 录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

 


PHP例子:

 

<?php 
$a=range(0,146); 
$high=count($a) - 1; 
$mid=0; 
$low=0; 
$found=0; 
$m=89;  //需要查找的值 
while( ($low<=$high) && ($found==0)){ 
    $mid=floor( ($low+$high) / 2 ); 
    if($m<$a[$mid])    
        $high=$mid-1; 
    elseif($m>$a[$mid])    
        $low=$mid+1; 
    else{ 
        $found=1; 
        $key=$mid; 
    } 
    $i++; 
} 
echo "共进行了{$i}次查找\n<br />\n"; 
echo "找到的下标是 {$mid}\n<br />\n"; 
echo "找到标志位 {$found}\n<br />\n"; 
?>
 
分享到:
评论

相关推荐

    折半查找算法在顺序表中插入一个元素讲解.pdf

    折半查找算法在顺序表中插入一个元素讲解 折半查找算法是一种常用的查找算法,它可以在已经排好序的顺序表中快速地找到某个元素。下面我们来详细讲解折半查找算法在顺序表中插入一个元素的过程。 折半查找算法的...

    顺序查找和折半查找

    折半查找,又称二分查找,是一种在有序数组中高效查找的方法。它利用了数组的索引特性,每次将待查找的区间减半,从而大大减少了查找次数。具体步骤如下: 1. 首先,找到数组中间的元素。 2. 如果中间元素等于目标值...

    折半查找的简单C语言算法

    使用折半查找,输入一个整数,查找是否在数组中,如在给出下标,否则-1

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

    折半查找算法,也称为二分查找算法,是一种在有序序列中快速定位特定元素的技术。由于其高效性和广泛的适用性,二分查找在计算机科学领域得到了广泛的应用,尤其在处理大数据量的有序数据时,其优势更为明显。本文将...

    折半查找 c语言函数

    折半查找,又称二分查找,是一种在有序数组中查找特定元素的搜索算法。它的基本思想是通过比较中间元素和目标值,将搜索范围不断缩小为一半,直到找到目标值或者搜索范围为空。这种方法相对于线性查找有显著的效率...

    折半查找算法的改进和程序实现

    折半查找算法,也称为二分查找算法,其基本原理是在有序数组中查找特定元素。该算法通过不断将搜索区间缩小为一半,直到找到目标值或搜索区间为空。尽管折半查找在时间复杂度上具有对数级别(O(log n)),但在处理大...

    查找算法:二分查找、顺序查找

    二分查找,也称为折半查找,是一种在有序数据集合中高效查找的算法。它利用了数组的索引特性,将查找过程分成一半再一半,直到找到目标值或者确定目标值不存在。 1. 首先,找到数据集的中间元素。 2. 检查中间元素...

    折半查找(二分查找)详解

    折半查找,又称二分查找,是一种在有序数据集合中高效搜索特定元素的算法。它主要应用于已排序的数组或列表,通过不断缩小搜索范围来提高查找效率。下面将详细介绍折半查找的基本思想、特点、适用场景以及具体的代码...

    折半查找法,也称为二分查找法.pdf

    折半查找法,又称二分查找法,是一种在有序数组中高效寻找目标值的算法。其核心思想是利用数组的有序性,通过不断缩小搜索范围,以递归或迭代的方式快速定位目标值。该方法特别适合于大规模数据的查找,因为它的平均...

    静态查找表。实现有序表的折半查找算法

    本篇文章将详细解释如何实现一个静态查找表,并利用折半查找算法(也称二分查找算法)来查询表中的数据。 #### 一、静态查找表的概念 静态查找表是一种只进行查找操作而不允许插入或删除操作的数据结构。其主要...

    数据结构中的折半查找程序代码

    数据结构中的折半查找程序,C语言描述,数据结构中的折半查找程序,C语言描述

    折半(二分)查找算法C语言源程序.zip

    折半查找,又称二分查找,是一种在有序数组中查找特定元素的搜索算法。它的基本思想是通过比较中间元素和目标值,将搜索范围不断缩小一半,直到找到目标元素或者搜索范围为空。这个方法非常高效,尤其对于大型有序...

    有序数组的折半查找

    折半查找,又称二分查找,是一种在有序数组中查找特定元素的搜索算法。相比传统的顺序查找,它具有更高的效率,尤其是在大型数据集上。折半查找的基本思想是利用数组的有序性,通过每次将查找区间缩小一半来快速定位...

    综合查找算法(顺序查找、折半查找、二叉排序树、哈希表)-数据结构课程设计

    本文将详细探讨四种常见的查找算法:顺序查找、折半查找、二叉排序树查找以及哈希表查找,并结合提供的"综合查找算法"课程设计项目,解析其在实际应用中的特点和优势。 **顺序查找**是最基础的查找算法,适用于任何...

    用折半查找法实现排序问题

    public int searchNumber(double num, boolean updown) {// 折半查找算法 int left = 0, right = Array.length - 1, middle = -1; while (left ) { middle = (left + right) / 2; if (num == Array[middle]) ...

    运用非递归方式设计折半查找法的程序.rar_折半查找

    【标题】:“运用非递归方式设计折半查找法的程序” 折半查找,也称为二分查找,是一种在有序数组中寻找特定元素的搜索算法。它的基本思想是每次将待搜索区域减半,直到找到目标元素或者确定目标元素不存在。这种...

    二叉排序树和折半查找

    折半查找,也称为二分查找,适用于有序数组。首先确定中间元素,然后与目标值比较。如果目标值小于中间元素,就在数组的左半部分继续查找;如果目标值大于中间元素,就在右半部分查找;如果相等,则查找成功。这个...

    折半查找 C语言 算法

    本篇将详细探讨C语言中的折半查找(Binary Search)算法,这是一种在有序数组中寻找特定元素的搜索算法,其效率远高于线性查找。 折半查找的基本思想源于二分法,它利用了数组的有序性。当数组已经排序时,我们可以...

    常见查找算法-折半查找的实现

    折半查找的实现 折半查找的实现 折半查找的实现 折半查找的实现 折半查找的实现

    C++折半查找代码实现

    折半查找(Binary Search),又称二分查找,是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间...

Global site tag (gtag.js) - Google Analytics