有序数组可以采用二分法查找关键字,先是一个有序数组类
package com.flysnow.chap02;
/**
* 递增有序数组,采用二分法查找数据
* @author 飞雪无情
* @since:2010-2-26
*/
public class OrdArray {
private int[] array;
private int nElem;
//构造函数
public OrdArray(int max){
array=new int[max];
}
public OrdArray(OrdArray array){
this.array=array.getArray();
this.nElem=array.size();
}
//数组的个数
public int size(){
return nElem;
}
/**
* 采用二分法查找数据
* @param searchKey 查找关键字
* @return 关键字的下标
*/
public int find(int searchKey){
int lowIndex=0;//最低下标
int highIndex=nElem-1;//最高下标
int index;//关键字的下标
while(true){
index=(lowIndex+highIndex)>>1;
if(array[index]==searchKey){//找到了
return index;
}else if(lowIndex>highIndex){
return nElem;//没有找到,返回数组的个数
}else{//还没有找完,继续查找
if(array[index]>searchKey){
highIndex=index-1;
}else{
lowIndex=index+1;
}
}
}
}
/**
* 插入数据
* @param value 要插入的数据
*/
public void insert(int value){
int j;
for(j=0;j<nElem;j++){
if(array[j]>value){
break;
}
}
//数据移位
for(int k=nElem;k>j;k--){
array[k]=array[k-1];
}
array[j]=value;
nElem++;
}
/**
* 删除数据
* @param value 要删除的数据
* @return 是否删除
*/
public boolean delete(int value){
int index=find(value);
if(index==nElem){//没有找到要删除的数据
return false;
}else{
for(int j=index;j<nElem;j++){
array[j]=array[j+1];
}
nElem--;
return true;
}
}
public int[] getArray() {
return array;
}
/**
* 显示
*/
public void display(){
for(int i=0;i<nElem;i++){
System.out.println("array["+i+"]:"+array[i]);
}
}
}
有序数组的插入、删除、查找测试
package com.flysnow.chap02;
/**
* @author 飞雪无情
* @since:2010-2-26
*/
public class OrdArrayApp {
/**
* @param args
*/
public static void main(String[] args) {
OrdArray array=new OrdArray(100);
array.insert(0);
array.insert(10);
array.insert(9);
array.insert(8);
array.insert(3);
array.insert(5);
array.insert(6);
array.insert(2);
array.insert(1);
array.insert(7);
array.insert(4);
array.display();
int searchKey=9;
//查找
int index=array.find(searchKey);
System.out.println(index==array.size()?"没有找到关键字:"+searchKey:"找到关键字下标为:"+index);
//删除
if(array.delete(searchKey)){
System.out.println("成功删除:"+searchKey);
array.display();
}else{
System.out.println("没有找到要删除的关键字:"+searchKey);
}
}
}
总结:有序数组的好处就是查找(二分法)速度快,但是插入的时候需要移动元素以腾出空间,所以较慢。
附上算法的复杂度的大O表示法图示:
- 大小: 16.8 KB
分享到:
相关推荐
如在有序一维数组[-10 , 3 , 4 , 11 , 22 , 43 , 49 , 56 , 90 , 90]中: -10 3 4 11 22 43 49 56 90 90 0 1 2 3 4 5 6 7 8 9 查90返回下标8 查30返回-1 数组的查找——二分法查找 设查找key的步骤(基本思想):...
二分法查找是一种常用的查找算法,也称为折半查找。...总之,二分法查找是一种常用的查找算法,适用于有序数组中查找某个元素的位置。通过将待查找区间缩小一半的方式,可以快速地定位目标元素,时间复杂度为O(log n)。
精简算法 二分法查找数组 算法精简查找效率高!
二分法查找 *进行二分法查找的前提是数组已有序 *查找范围的上下界
本文实例讲述了C++二分法在数组中查找关键字的方法。分享给大家供大家参考。具体如下: /* 此程序演示了二分法查找算法(针对按从小到大排列的数组)的实现。 */ #include using namespace std; /* 功能: 实现...
易语言有序二分法查找源码,有序二分法查找,算法_二分法
设计函数能够用二分法查找元素对应下标,同时可以检测出用户是否输入有误,鲁棒性较好。
易语言源码有序二分法查找易语言源码.rar 易语言源码有序二分法查找易语言源码.rar 易语言源码有序二分法查找易语言源码.rar 易语言源码有序二分法查找易语言源码.rar 易语言源码有序二分法查找易语言源码.rar ...
本文实例讲述了Python有序查找算法之二分法。分享给大家供大家参考,具体如下: 二分法是一种快速查找的方法,时间复杂度低,逻辑简单易懂,总的来说就是不断的除以2除以2… 例如需要查找有序数组arr里面的某个...
c 二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法...
初始化一个已排序的整型数组,用二分法查找其中是否存在常量5,如有,打印其下标。
C语言实现的二分法快速查找|二分法排序|二分法查找C#
题目: 编程实现找出一组数的最大值和次大值 要求: 用二分法的策略实现; (2)写出实验报告。 一、 需求分析: 1、输入要输入数组元素的个数,为数组... 3、利用二分法找出数组中的最大值和次大值; 4、输出结果;
在一个数组中,查找指定值,如果这个值在数组中存在,则返回该值的元素下标,表示能找到;如果不存在,则可以返回一个负的值 ,表示找不到。 11 22 43 90 4 90 56 49 -10 3 0 1 2 3 4 5 6 7 8 9 线性查找 二分法查找...
二分法查找法
java 二分法查找案例与数组排序案例
关于二分法查找的课件,特别容易懂,特此推荐给大家
=0 and $high == 0) //判断是否为第一次调用 { $high = count($array); } if($low <= $high) //如果还存在剩余的数组元素 { $mid = intval(($low+$high)/2); //取$low和$high的中间值 if ($array[$mid
有序二分法查找易语言源码。@资源源码站。