当前位置:首页 » 《随便一记》 » 正文

2021-09-18_北小方的博客

2 人参与  2021年12月21日 08:19  分类 : 《随便一记》  评论

点击全文阅读


算法——二分法查找与二分法插入排序

1.二分法查找(binarySearch)

众所周知,古代有一种查找方式:100个数内通过五次得出一个人心里想的数字,这便是二分法查找。
二分法查找,也称为折半法查找,是一种在有序数组中查找特定元素的搜索算法。以下便是其思路:
1)在数组两端插入两个区域限制数据,然后从数组的中间元素开始搜索,如果该元素是目标元素,则搜索过程结束,若不为目标元素,则开始执行下一步
2)若目标元素小于中间元素((最大值+最小值)/2),则右节点移至中间元素,若目标元素大于中间元素,则左节点移至中间元素。该步骤结束后开始进行下一次查找,重复(1)的操作。
3)直到左节点与右节点指向同一个元素,那么该元素为目标元素,至此跳出循环。
有了以上思路,便可以写出代码:

#include<iostream>

using namespace std;

void halfSerch(int* a, int number, int n)
{
	int min = 0;
	int max = n - 1;
	int timenumber = 0;
		while (min<max)
		{
		//获取中间点
		int mid = (max + min) / 2;
		//获取中间节点成功,跳出循环,得到查找的次数
		if (a[mid] == number)
		{
			timenumber++;
			cout << "查找了" << timenumber << "次" << endl;
			cout << "查找到的最终值为" << a[mid] << endl;
			break;
		}
		//中间值小于设定值,最小值变为中间值+1,查找次数+1
		else if (a[mid] < number)
		{
			min = mid + 1;
			timenumber++;
		}
		//中间值小于设定值,最大值变为中间值-1,查找次数+1
		else if (a[mid]>number)
		{
			max = mid - 1;
			timenumber++;
		}
		}
}

int main()
{
	int a[10];
	int n, number;
	cout << "输入数组大小";
	cin >> n;//(n<=10)
	for (int i = 0; i < n; i++)
	{
		cout << "输入第"<<i+1<<"个数组的值";
		cin >> a[i];
	}
	cout << "输入设定的值";
	cin >> number;
		halfSerch(a, number, n);
}

运行结果:
二分法查找结果

得到该算法后,可以算出时间复杂度:
由该题意可得:数据长度为N,每次查找后减半。
第一次为:N/2
第二次为:N/4
.
.
.
第n次为:N/(2^n)
最差的情况是:最终数据长度为1,所以有:
N/(2^n) = 1;
所以可得出n=log2(N);
而最好的情况是第一次
因此该算法时间复杂度位O(log2(N))

2.二分法插入排序(折半法排序)

二分法插入排序与插入排序在本质上都没有区别,都是从无序序列中取出数据和有序序列进行对比,放到合适位置。
但是它俩的区别在于:
虽然两者都是对待排序的数,插入到前面已经排好序的数组中,并且时间复杂度都为O(1)~O(n^2),但是相比于直接插入排序,二分法插入排序减少了比较的次数,平均的性能优于直接插入排序。
程序如下:

#include<iostream>

using namespace std;

//二分法插入排序
void insertBinary(int* a, int n){
	int i, j, tmp;
	int low, mid, high;
	for (i = 1; i<n; i++){
		tmp = a[i];
		low = 0; high = i - 1;
		/* 1.寻找插入位置J */
		while (low <= high){
			mid = (low + high) / 2;
			if (tmp>a[mid]) low = mid + 1; //如果取的数据比中间的大,则说明需要在mid右边寻找位置J
			else high = mid - 1;
		}
		/* 2.后移插入位置 */
		//从位置i到位置J(low/high)依次后移动一位 
		for (j = i; j>low; j--){
			a[j] = a[j - 1];
		}
		a[low] = tmp;
	}
}

int main()
{
	int a[10] = { 5, 2, 1, 3, 9, 4, 6, 7, 0, 8 };
	insertBinary(a, 10);
	for (int i = 0; i < 10; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}

运行结果:
在这里插入图片描述

对于比较少的数据,二分法插入排序体现不到很多优点,但是若有大量的数据需要排序,则二分法插入排序相较于插入排序更能优化运算性能。


点击全文阅读


本文链接:http://zhangshiyu.com/post/31810.html

插入  排序  元素  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 当女配看见弹幕后,被病娇男主强制爱了续集(裴纪洲江柠)_当女配看见弹幕后,被病娇男主强制爱了续集(裴纪洲江柠)
  • 「都市:比悍匪还猛,你管这叫警察?」章节限时抢先看‌_[苏浩]精彩章节免费试读
  • [乖乖女甜又野,偏执贺总失控沦陷]全集阅读_「温黎贺行舟」完结版免费阅读
  • 当女配看见弹幕后,被病娇男主强制爱了+结局+番外(裴纪洲江柠)列表_当女配看见弹幕后,被病娇男主强制爱了+结局+番外
  • 沈青禾霍沉洲+后续+结局(沈青禾霍沉洲)列表_沈青禾霍沉洲+后续+结局(沈青禾霍沉洲)全书+后续+结局在线
  • 全文当女配看见弹幕后,被病娇男主强制爱了+结局+番外(裴纪洲江柠)列表_全文当女配看见弹幕后,被病娇男主强制爱了+结局+番外
  • 当女配看见弹幕后,被病娇男主强制爱了结局+番外免费_(裴纪洲江柠)当女配看见弹幕后,被病娇男主强制爱了结局+番外列表_笔趣阁(裴纪洲江柠)
  • 当女配看见弹幕后,被病娇男主强制爱了+后续+结局(裴纪洲江柠)_(当女配看见弹幕后,被病娇男主强制爱了+后续+结局)列表_笔趣阁(裴纪洲江柠)
  • 陆斐年沈卿卿(偏我情深一往结局+番外)完结_(陆斐年沈卿卿)列表_笔趣阁(偏我情深一往结局+番外)
  • 全文桃花依然笑春风(陆乘渊云梵音)列表_全文桃花依然笑春风
  • 半是风雨半是霜全书+后续+结局(顾宴辞宋相欢)免费_(半是风雨半是霜全书+后续+结局)顾宴辞宋相欢列表_笔趣阁(顾宴辞宋相欢)
  • 人面桃花长相忆+后续+结局(阮雾梨闻砚辞阮见微)_(人面桃花长相忆+后续+结局)列表_笔趣阁(阮雾梨闻砚辞阮见微)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1