萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

二分查找

发表于 2019-07-23 | 分类于 算法学习日记 | 0 | 阅读次数 586
  • 别名:折半查找

  • 时间复杂度:O(log2n)

  • 优点:查找速度快

  • 缺点:待查表为有序表

  • 算法要求:

  1. 必须采用顺序存储结构。
  2. 必须按关键字大小有序排列。
  • 查找过程: 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

  • 代码演示

  1. C/C++:1
int BinSearch(SeqList *R,int n,KeyType K)
{
	//在有序表R[0..n-1]中进行二分查找,成功时返回结点的位置,失败时返回-1
	int low=0,high=n-1,mid;     //置当前查找区间上、下界的初值
  	while(low<=high)
  	{
  		if(R[low].key==K)
  			return low;
  		if(R[high].key==k)
  			return high;//当前查找区间R[low..high]非空
		mid=low+(high-low)/2;
					
	/*使用(low+high)/2会有整数溢出的问题
	(问题会出现在当low+high的结果大于表达式结果类型所能表示
	的最大值时,这样,产生溢出后再/2是不会产生正确结果的,
	而low+((high-low)/2)不存在这个问题
	*/
		
		if(R[mid].key==K)
			return mid;   //查找成功返
		if(R[mid].key<K)
			low=mid+1;   //继续在R[mid+1..high]中查找
		else
			high=mid-1;   //继续在R[low..mid-1]中查找
	}
  	if(low>high)
  		return -1;//当low>high时表示所查找区间内没有结果,查找失败
}


  1. C/C++:2:
int bsearchWithoutRecursion(int array[],int low,int high,int target)
{
  	while(low<=high)
  	{
  		int mid=low+(high-low)/2;//还是溢出问题
  		if(array[mid]>target)
  			high=mid-1;
  		else if(array[mid]<target)
  			low=mid+1;
  		else
			return mid;
  	}
  	return -1;
}
  1. C/C++:3
int binSearch(const int *Array,int start,int end,int key)
{
	int left,right;
  	int mid;
  	left=start;
  	right=end;
  	while(left<=right)
  	{
		mid=left+(right-left)/2;//还是溢出问
		if(key==Array[mid])  return mid;
  		else if(key<Array[mid]) right=mid-1;
		else if(key>Array[mid]) left=mid+1;
  	}
  	return -1;
}

  1. C/C++:递归
#include<iostream>
using namespace std;
int a[100]={1,2,3,5,12,12,12,15,29,55};//数组中的数(由小到大)
int k;//要找的数字
int found(int x,int y)
{
	int m=x+(y-x)/2;
	if(x>y)//查找完毕没有找到答案,返回-1
		return -1;
	else
  	{
  		if(a[m]==k)
			return m;//找到!返回位置.
  		else if(a[m]>k)
			return found(x,m-1);//找左边
  		else
			return found(m+1,y);//找右边
	}
}
int main()
{
	cin>>k;//输入要找的数字c语言把cin换为scanf即可
	cout<<found(0,9);//从数组a[0]到a[9]c语言把cout换为printf即可
  	return 0;
}

  1. Java
public static int binarySearch(Integer[] srcArray, int des) {
  	//定义初始最小、最大索引
	int low = 0;
  	int high = srcArray.length - 1;
  	//确保不会出现重复查找,越界
  	while (low <= high) {
		//计算出中间索引值
		int middle = (high + low)>>>1 ;//防止溢出
		if (des == srcArray[middle]) {
 	 		return middle;
  		//判断下限
		} else if (des < srcArray[middle]) {
  			high = middle - 1;
  		//判断上限
		} else {
  			low = middle + 1;
		}
	}
	//若没有,则返回-1
  	return -1;
}

文章参考

# 算法 # 程序设计
致即将或刚刚进入大学的计算机专业同学
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

77 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持