二分查找（binary search）

迈不过友情╰ 2022-08-20 13:10 116阅读 0赞

**二分查找**:又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。

实例代码：

//binary search array
    #include "stdafx.h"
    #include <iostream>
    using std::cout;
    using std::endl;
    
    int BinarySearch(int *data, int nLen, int nSought)
    {
    	if (nLen < 1)
    	{
    		return -1;
    	}
    
    	int low = 0;
    	int hight = nLen - 1;
    	int mid = (low + hight) / 2;
    	while (low <= hight)
    	{
    		if (data[mid] == nSought)
    		{
    			return mid;
    		}
    		else if (data[mid] < nSought)
    		{
    			low = mid + 1;
    		}
    		else
    		{
    			hight = mid - 1;
    		}
    
    		mid = (low + hight) / 2;
    	}
    
    	return -1;
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int data[] = { 1, 3, 4, 5, 7, 9 };
    	int nlen = sizeof(data) / sizeof(int);
    	int nSought = 6;
    	int nret = BinarySearch(data, nlen, nSought);
    	if (nret == -1)
    	{
    		cout << "没有查找到: " << nSought << endl;
    	}
    	else
    	{
    		cout << nSought << " 索引是：" << nret << endl;
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，116人围观）

还没有评论，来说两句吧...

相关阅读

相关基础算法练习02--二分查找（Binary Search）

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列 -- 百度百科

刺骨的言语ヽ痛彻心扉/ 2024年02月19日 13:57/ 0 赞/ 7 阅读

相关 LeetCode 704. Binary Search (二分查找)

题目标签：Binary Search 　　很标准的一个二分查找，具体看code。 Java Solution: Runtime: 0 ms, faster tha

客官°小女子只卖身不卖艺/ 2023年08月17日 16:45/ 0 赞/ 87 阅读

相关 java 如何实现 binary search 二分查找法？

![思维导图][8afab1b810940c5f1fe313359874c578.png] 顺序查找如果让你在一堆书架上找到自己想要的书，你会怎么找呢？实际上最简

水深无声/ 2022年12月24日 12:54/ 0 赞/ 52 阅读

相关 STL算法 | 查找函数 find()、二分查找binary_search/upper_bound、子序列查找search

文章目录一、find系列函数（单个元素顺序查找） 1. find 搜索等于 value 的元素。 2. find\_if

亦凉/ 2022年10月30日 12:26/ 0 赞/ 131 阅读

相关二分查找（binary search）

二分查找:又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。实例代码： //binary search arra

迈不过友情╰/ 2022年08月20日 13:10/ 0 赞/ 117 阅读

相关 LeetCode: Binary Search Modification (二分查找的变型)

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。 > > 这博客是记录我学习的点点滴滴，如果您对 Python、Java

青旅半醒/ 2022年05月14日 16:38/ 0 赞/ 60 阅读

相关 Binary Search

简单的二分搜索：在一个非递减序整型数组中搜索值value，返回其所在下标最普通的二分搜索 ![ContractedBlock.gif][] ![ExpandedBloc

喜欢ヅ旅行/ 2022年04月01日 13:50/ 0 赞/ 128 阅读

相关 STL中的二分查找——lower_bound 、upper_bound 、binary_search

二分查找很简单，原理就不说了。STL中关于二分查找的函数有三个lower\_bound 、upper\_bound 、binary\_search 。这三个函数都

蔚落/ 2022年03月19日 08:38/ 0 赞/ 150 阅读

相关二叉查找树（Binary Search Tree）

Date：2019-06-25 14:40:32 基本操作注意：数据量较大时，插入建树的时间复杂度会很高，慎用！ 1 //查找 2 vo

深碍√TFBOYSˉ_/ 2021年12月20日 06:29/ 0 赞/ 177 阅读

相关二分查找法 Binary Search

二分查找法 Binary Search 在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中

今天药忘吃喽~/ 2021年11月23日 06:30/ 0 赞/ 197 阅读