双重检验锁 asynchronous gridview proxy xampp Seajs vue过滤器 vue树形菜单 大数据项目开发案例 mysql批量更新数据 hbase端口 idea整理代码 matlab不等于怎么表示 python中文文档 python的lambda函数 java的数据结构 java写文件 学java基础 java框架学习 java连接mysql的jar包 java获取当前日期 java特性 linux启动 linux硬盘 python源码下载 制作字幕的软件 易语言多线程 c语言程序100例 福昕阅读器绿色版 工信部手机入网查询 苹果手机添加邮箱 js转数字 c4d挤压怎么用 重复文件查找软件 五子棋大师 qq流览器下载 冬青黑体简体中文 分割字符串 proxies 淘宝退货怎么上门取件
当前位置: 首页 > 学习教程  > 编程语言

二分搜索

2021/1/28 22:43:44 文章标签:

二分查找 顾名思义,二分查找就是将原来要查找的序列一分为二,以优化查找的效率。二分查找的基本思想: 输入为有序的序列。取中间元素与待查找元素x进行比较,如果x等于中间元素,则算法终止;如x小于中间元素&…

二分查找


  • 顾名思义,二分查找就是将原来要查找的序列一分为二,以优化查找的效率。
  • 二分查找的基本思想:
    • 输入为有序的序列。
    • 取中间元素与待查找元素x进行比较,如果x等于中间元素,则算法终止;
    • 如x小于中间元素,则在序列的 左半部 继续查找。否则,在序列的 右半部
  • 直接上代码,看注释
#include <iostream>
#include <algorithm>

/*二分查找函数实现及使用库函数实现*/

using namespace std;

/**
 * 二分查找元素在有序数组中的位置 
 * @param a 指向目标数组的指针
 * @param len 数组的长度
 * @number number 要查找元素
 * @return 查找到返回元素的下标;查找不到,返回-1;
 */
int bin_search(int *a, int len, int number) {
	if (a == NULL || len < 0) {
		cout << "The param is illegal" << endl;
		return -2;
	}
	int left = 0, right = len;
	cout << "left is " << left << endl;
	cout << "right is " << right << endl;
	/*取中间元素进行比较*/
	int mid = (left + right) / 2;
	while (left < right) {
		if (a[mid] == number) {
			/*找到了,直接返回下标*/
			return mid;
		}
		else {
			if (a[mid] < number) {
				/* 因为mid左边的元素都比mid要小,根据'<'的传递性,
				 * mid及其左边的元素都要小于number,所以number不在左边。
				 * 那么,如果number在数组中,就只可能在右边,所以将区间缩小为右半区间*/
				left = mid + 1;
				cout << "left convert to " << left << endl;
			}
			else {
				/*和上面是同理的,只是情况不同,将区间缩小为左半区间*/
				right = mid - 1;
				cout << "right convert to " << right << endl;
			}
		}
		if (mid < 0 || mid > len + 1) {
			break;
		}
		mid = (left + right) / 2;
	}
	return -1;
}

int main() {
	int a[] = {9,3,4,1,5,6,2,7};
	/*先进行排序*/
	sort(a, a + sizeof(a) / sizeof(int));
	/*打印一下排序之后的结果*/
	for (int i = 0; i < sizeof(a) / sizeof(int); i++) {
		cout << a[i] << " ";
	}
	cout << endl;

	int number;
	cout << "Please cin the number you want to find:";
	cin >> number;
	/*使用上面的函数进行查找*/
	int res = bin_search(a, sizeof(a) / sizeof(int), number );

	cout << "The result is " << res << endl;

	cout << "__________________________________________" << endl;
	/*使用库函数进行查找*/
	bool flag = binary_search(a, a + sizeof(a) / sizeof(int), number);
	if (flag) {
		cout << "found" << endl;
	}
	else {
		cout << "not found" << endl;
	}
	return 0;
}

本文链接: http://www.dtmao.cc/news_show_650072.shtml

附件下载

上一篇:2020.1.28 Leetcode刷题

下一篇:1月28日总结

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?