一:概念
二分查找又称折半查找(折半搜索/二分搜索),优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而 查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表 分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录, 使查找成功,或直到子表不存在为止,此时查找不成功。
二:原理
二分查找的基本思想是:(设R[low..high]是当前的查找区间)(1)首先确定该区间的中点位置:
mid=(low+high)/2
(2)然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,具体方法如下:
①若R[mid].key>K,则由表的有序性可知R[mid..n].keys均大于K,因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R[1..mid-1]中,故新的查找区间是左子表R[1..mid-1]。
②类似地,若R[mid].key<K,则要查找的K必在mid的右子表R[mid+1..n]中,即新的查找区间是右子表R[mid+1..n]。下一次查找是针对新的查找区间进行的。
因此,从初始的查找区间R[1..n]开始,每经过一次与当前查找区间的中点位置上的结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点,或者直至当前的查找区间为空(即查找失败)时为止。
三:用JAVA实现
publicstaticint binarySearch2(int[] srcArray,int des) throws Exception{ int beginIndex = 0; int endIndex = srcArray.length-1; int middleIndex = beginIndex+((endIndex-beginIndex)>>1); while(srcArray[middleIndex] != des && endIndex > beginIndex && (endIndex-1)>beginIndex){ if(srcArray[middleIndex] < des){ beginIndex = middleIndex; }elseif(srcArray[middleIndex] > des){ endIndex = middleIndex; } middleIndex = beginIndex+((endIndex-beginIndex)>>1); } if(srcArray[middleIndex] == des){ return middleIndex; //表示找到了,返回该值的下标 }else{ thrownew Exception("没有找到"); //表示没有找到 } }上面这是自己根据对二分查找算法原理的理解写出来的代码。
下面的是摘自己网上的写法:
public static int binarySearch3(int[] srcArray,int des) throws Exception{ int beginIndex = 0; int endIndex = srcArray.length-1; while(beginIndex <= endIndex){ int middleIndex = beginIndex+((endIndex-beginIndex)>>1); if(srcArray[middleIndex] < des){ beginIndex = middleIndex+1; }else if(srcArray[middleIndex] > des){ endIndex = middleIndex-1; }else{ return middleIndex; } } throw new Exception("没有找到");//表示没有找到 }
相关推荐
二分查找排序算法是一种高效的排序方法,它是基于二分查找思想和插入排序的结合体。在计算机科学中,排序算法是处理数据集合的一种基础方法,它使得数据按照特定的顺序排列,例如升序或降序。二分查找排序算法特别...
论文首先介绍了算法分析的目的和重要性,然后对二分查找排序法的时间复杂度进行了详细的分析。 在算法分析中,时间复杂度是指程序运行从开始到结束所需要的时间。它通常用大O符号表示,例如O(n)表示算法的执行时间...
二分查找算法与冒泡排序算法是计算机科学中两种基础且重要的算法,它们在数据处理和数组操作中扮演着至关重要的角色。 首先,我们来详细探讨递归二分查找算法。二分查找,也称为折半查找,是一种在有序数组中查找...
在这个主题中,我们主要关注查找和排序算法,特别是二分查找(折半查找)算法。这些算法在实际编程中具有广泛应用,包括数据库索引、搜索引擎优化和各种计算问题的解决。 首先,我们来看查找算法。查找是数据结构中...
- 在排序算法中,例如快速排序和归并排序,也会用到二分查找。 通过理解二分查找算法的工作原理,熟练掌握其C++实现,并结合实际应用场景,我们可以有效地提高程序的运行效率。对于学习计算机科学的学生和专业...
二分查找算法是计算机科学中的一个基本算法,适用于任何已排序的列表或数组。其优势在于能够快速地定位到目标值所在的范围,从而大幅减少不必要的比较次数。此外,对于大规模数据集而言,二分查找的效率远高于线性...
**二分查找与分治算法详解** 二分查找是一种基于分治策略的高效搜索算法,主要应用于有序数据集合。在给定的升序排列的数组a[0:n-1]中,二分查找的目标是找到特定元素x的位置,或者确认元素不在数组中。算法的基本...
【快速排序】是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。其基本思想是采用分治法,通过选取一个基准元素,将待排序序列分为两个子序列,使得一个子序列的所有元素都小于基准,另一个子序列...
二分查找(Binary Search)是计算机科学中一种高效的数据检索方法,适用于已排序的数组或列表。它的基本思想是将目标值与数组中间元素进行比较,如果目标值等于中间元素,则查找成功;如果目标值小于中间元素,则在...
在Java编程中,文件读取、数组操作、选择排序以及二分查找是常见的编程任务,它们涉及了IO流、数据结构和算法等多个方面。以下是这些知识点的详细解释: 1. **文件读取**:Java提供了丰富的IO流类库用于读取文件。...
4. **二分查找**: 实现了`bin_search`函数,用户输入待查找的学生学号,通过二分查找法定位学号位置,找到则输出相关信息,否则提示未找到。 5. **直接插入排序**: 直接插入排序是一种简单的排序算法,通过构建有序...
不同之处在于,归并排序不使用二分查找,而是将数组分为两半,然后对每一半进行排序,再合并。归并排序在MATLAB中实现时,也需要递归地将数组划分为更小的部分,直到每个部分仅包含一个元素,然后逐步合并这些元素,...
本资源“C#经典排序算法大全和二分查找算法”提供了多种经典的排序算法实现,以及C#中的二分查找算法。让我们深入探讨这些算法的原理、实现方式以及它们在实际开发中的应用。 首先,我们来看一下排序算法。排序是将...
快速排序是一种高效的排序算法,而二分查找则是一种在有序序列中寻找特定元素的有效方法。 快速排序由英国计算机科学家C.A.R. Hoare在1960年提出,它的基本思想是采用分治法。首先选择一个基准值,将数组分为两部分...
二分查找算法是一种高效的数据搜索方法,主要应用于已排序的序列。它的基本思想是通过不断地将待搜索区域减半来快速定位目标值。这个过程基于分治策略,将大问题分解为更小的子问题来解决。在二分查找算法中,每次...
在IT领域,二分查找算法(也称为折半查找)是一种高效的搜索算法,尤其适用于已排序的数据集合。这种算法利用了有序数据集的特点,通过不断缩小查找范围来快速定位目标值。在本案例中,"winform 二分查找算法源码" ...
需要注意的是,二分查找的前提是数据必须有序,因此在实际应用中,通常需要先对数据进行排序,例如使用快速排序、归并排序等。此外,二分查找在大数据量时表现优异,适用于索引查找和数据库查询等领域。 二分查找...
本资料包涵盖了数据结构的各种查找排序算法的实现,以及相关的习题、试卷和答案,非常适合学习者深入理解和实践。 首先,让我们来看看查找算法。查找算法的目标是在数据集合中找到特定的元素。常见的查找算法有线性...
二分查找(非递归) <*******\n"); printf("\t***********> 3.二分查找(递归) <*******\n"); printf("\t***********> 4,直接插入排序 <*******\n"); printf("\t***********> 5.直接选择排序 <*******\n"); ...