http://student.zjzk.cn/course_ware/data_structure/web/chazhao/chazhao9.2.2.1.htm
1、二分查找(Binary Search)
二分查找又称折半查找,它是一种效率较高的查找方法。
二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。
2、二分查找的基本思想
二分查找的基本思想是:(设R[low..high]是当前的查找区间)
(1)首先确定该区间的中点位置:
(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的结点,或者直至当前的查找区间为空(即查找失败)时为止。
3、二分查找算法
int BinSearch(SeqList R,KeyType K)
{ //在有序表R[1..n]中进行二分查找,成功时返回结点的位置,失败时返回零
int low=1,high=n,mid; //置当前查找区间上、下界的初值
while(low<=high){ //当前查找区间R[low..high]非空
mid=(low+high)/2;
if(R[mid].key==K) return mid; //查找成功返回
if(R[mid].kdy>K)
high=mid-1; //继续在R[low..mid-1]中查找
else
low=mid+1; //继续在R[mid+1..high]中查找
}
return 0; //当low>high时表示查找区间为空,查找失败
} //BinSeareh
4、 二分查找算法的执行过程
设算法的输入实例中有序的关键字序列为
(05,13,19,21,37,56,64,75,80,88,92)
http://guiqing85.iteye.com/blog/538019
Java版二分查找算法
二分查找算法的目标查找集合应该为有序序列
/*
* @(#)BinarySearch.java 2009-8-8
*
* Copyright (c) 2009 by jadmin. All Rights Reserved.
*/
package algorithm.search;
/**
* 二分查找算法
*
* @author <a href="mailto:jadmin@126.com">jadmin</a>
* @version $Id: BinarySearch.java 2009-8-8 上午05:07:05$
* @see <a href="http://hi.baidu.com/jadmin">myblog</a>
*/
public final class BinarySearch {
public static int find(int[] a, int key) {
return find(a, 0, a.length - 1, key);
}
// 非递归实现
public static int find(int[] a, int fromIndex, int toIndex, int key) {
int low = fromIndex;
int high = toIndex;
while (low <= high) {
// 无符号右移位逻辑运算
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
// 递归实现
public static int search(int[] a, int fromIndex, int toIndex, int key) {
if(fromIndex > toIndex) {
return -1;
}
int mid = (fromIndex + toIndex) >>> 1;
if(a[mid] < key) {
return search(a, mid + 1, toIndex, key);
} else if(a[mid] > key) {
return search(a, fromIndex, mid - 1, key);
} else {
return mid;
}
}
分享到:
相关推荐
折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)
二分查找算法,二分查找算法课件,二分查找算法PPT
二分查找_测试
二分查找算法
简单地实现了二分查找的可视化。界面很简单就包括两个部分:界面左侧是可视化查找部分,右侧是二分查找的代码。 程序的关键点主要有两点: 1. 如何在页面上表示出查找程序的运行过程。 2. 如何将排序程序的运行...
1.二分查找又称为折半查找,它要求要查找的顺序表必须是有序表,即表中结点按关键字有序.并且要用顺序存储结构。 基本思想是:首先将给定值key与表中中间位置记录的关键字相比较,若二者相等,则查找成功,否则...
二分查找 C语言语言源代码 用递归写的 C语言入门经典代码 值得收藏
//二分查找 #include const int MAXN=10010; using namespace std; //二分查找,递归实现 int binarySearch(int a[],int low,int high,int key) { //查找某元素是否在数组中,若存在,则返回下标,否则...
二分查找
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表...
二分查找
VB 二分查找 VB 二分查找 VB 二分查找
s[middle] 关键字小于中值 继续二分查找 并将上限改为middle BinarySearch s x low middle 1 ; else 关键字大于中值 继续二分查找 并将下限改为middle BinarySearch s x middle + 1 high ;">if high < low ...
二分查找ppt
一、实验目的: 熟悉各种查找算法及其复杂性,能够根据实际情况选择合适的存储结构。 二、实验要求: 1、掌握查找的基本方法。 2、提交实验报告,报告...编程分别对有序顺序表的顺序查找,二分查找算法进行实现。
int BinSearch(SeqList R,int n,KeyType k) /*二分查找算法*/ { int low=0,high=n-1,mid,count=0; while (low) { mid=(low+high)/2; printf("第%d次查找:在[%d,%d]中查找到元素R[%d]:%d\n",++count,low,high,...
文件读出数组进行选择排序和二分查找文件读出数组进行选择排序和二分查找java实现
设计一个程序,建立由有序序列R[0..n-1]进行二分查找产生的判定树,在此基础上完成如下功能: (1) 输出n=11时的判定树并求成功情况下的平均查找长度ASl (2) 通过构造判定树可以求得的成功情况下的平均查找长度...
C++ 二分查找法