二分查找算法


二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

Golang二分查找算法的简单实现

二分查找改进版

二分查找的实现及注意事项

用Python实现二分查找

二分查找之Java实现

Java针对数组的普通查找法和二分查找法

算法要求:

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

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

下面是c++与java的不同实现:

已经假设所查询数组均为升序排列好了:

C++版:

#include <iostream>
#include <stdlib.h>
#define  ERROR -1
#define LEN 10
using namespace std;
/************************************************************************/
/*  T  自定义数据类型
 value 查找的值
 low  左侧边界 (一般为0)
 high    右侧边界(一般为数组长度-1)
/************************************************************************/
template <class T>
int binarySearch(T table[],T value,int low,int hign){
 if(low<=hign){//边界有效
  int mid = (low+hign)/2; //找到中间点
  if(table[mid]==value){//如果中间点的值就是我们查找的值,则返回该点
   return mid;
  }else if(table[mid]>value){//如果中间值比查找值大,则证明查找的值在中间点的左侧
   return binarySearch(table,value,low,mid-1);//继续将范围缩小到原来一半(靠左缩小)
  }else{
   return binarySearch(table,value,mid+1,hign);//继续将范围缩小到原来一半(靠右缩小)
  }
 }
 return ERROR;
}
/************************************************************************/
/* 由上述代码可以知道,上边界和和下边界其实就是数组的开始和结束位置,因此上述函数可以泛化为下列函数                                                                    */
/************************************************************************/
template <class T>
int binarySearch(T table[],int n,T value){
 return binarySearch(table,value,0,n-1);
}
template <class T>
void print(T table[],int n){
 for (int i=0;i<n;i++)
 {
  cout<<table[i]<<" ";
 }
 cout<<"\n";
}
int main(void){

 //给出一个已经排序好的数组
 int array[LEN] = {0};
 for (int i=0;i<LEN;i++)
 {
  array[i] = i+10;
 }
 cout<<"您要查找的序列为:";
 print(array,LEN);
 cout<<"请输入你要查找的内容:";
 int search;
 cin>>search;
 //调用函数
 int searchResult = binarySearch(array,LEN,search);
 cout<<"查找内容为"<<search<<"在指定数组的第"<<(searchResult+1)<<"处"<<endl;
 system("pause");
 return 1;
}

本文永久更新链接地址：

相关内容