C++数据结构与STL--二分查找

偏执的太偏执、 2021-12-16 08:53 252阅读 0赞

**给出数组int arr\[\]=\{-7,3,5,8,12,16,23,33,55\};**

**\*查找target=23**

**![20130725213829531][]**

**\#include<iostream>  
using namespace std;  
template<typename T>  
//查找成功则返回元素下标，否则返回-1  
//数组查找下标范围\[begin,last)  
//此二分查找算法要求数组中的元素已经按从小到大排序   
int binarySearch(T arr\[\],int begin,int last,T val)  
\{  
T midValue;  
int midIndex;  
while(begin<last)  
\{  
midIndex=(begin+last)/2;  
midValue=arr\[midIndex\];  
if(midValue==val)  
\{  
return midIndex; //查找成功   
\}  
else if(midValue<val)  
\{   
begin=midIndex+1;//重定义begin，以便继续查找\[midIndex+1,last)部分   
\}  
else  
\{   
last=midIndex;//重定义last，以便继续查找\[begin,midIndex)半部分  
\}  
\}  
return -1;//查找失败   
\}  
  
  
int main()  
\{   
int arr\[\]=\{-7,3,5,8,12,16,23,33,55\};  
int index=binarySearch(arr,0,9,23);//测试查找数组范围内的元素   
cout<<index<<endl;//6  
int index1=binarySearch(arr,0,9,60);//测试查找超出数组右边界的元素  
cout<<index1<<endl;//-1;  
int index2=binarySearch(arr,0,9,-8);//测试查找超出数组左边界的元素  
cout<<index2<<endl;//-1   
  
char ch\[\]=\{'a','b','c','d'\};  
int index3=binarySearch(ch,0,4,'b');//测试其他数据类型的数组   
cout<<index3<<endl;//1  
return 0;  
\}**

[20130725213829531]: /images/20211214/d116866b54c141238ac54d4fdabcd548.png

发表评论取消回复

表情：

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

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

相关阅读

相关【数据结构与算法】二分查找

一、什么是二分查找？二分查找针对的是一个有序的数据集合，每次通过跟区间中间的元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0。二、

客官°小女子只卖身不卖艺/ 2022年11月28日 13:33/ 0 赞/ 140 阅读

相关【数据结构与算法】二分查找

基本思想首先将给定的值K与表中中间位置元素比较，若相等，则查找成功；若不等，则所需查找的元素只能在中间数据以外的前半部分或者后半部分，缩小范围后继续进行同样的查找，如

短命女/ 2022年08月11日 00:55/ 0 赞/ 208 阅读

相关数据结构（二分查找）

折半查找又叫二分查找，其基本思想是：在有序表中，取中间记录作为比较对象，如果查找的记录的关键码等于中间记录的关键码，则查找成功；若小于，则在左半区查找；若大于，则在右半区查找。

墨蓝/ 2022年06月05日 12:50/ 0 赞/ 193 阅读

相关 C语言数据结构之排序与查找数据结构实验之查找四：二分查找

数据结构实验之查找四：二分查找 Time Limit: 30MS Memory Limit: 65536KB Submit Statistic Problem De

清疚/ 2022年05月31日 01:53/ 0 赞/ 186 阅读

相关数据结构与算法-二分查找

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

Love The Way You Lie/ 2022年05月29日 10:00/ 0 赞/ 223 阅读

相关二分查找-查找算法-数据结构与算法

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

迷南。/ 2022年02月12日 12:23/ 0 赞/ 329 阅读

相关 JS数据结构与算法——二分查找

/ 二分查找 @param {Array} arr 待查找数组,数组需要已按照从小到大排序 @param {Any} x 待查找项 @return {Numbe

心已赠人/ 2022年02月02日 02:51/ 0 赞/ 276 阅读

相关 c语言数据结构二分查找算法

/\ \二分查找算法(对已经排好序的数据而言) \设置一个 L M H 三个临时变量将排好序的数组 \分别对应第一个元素的下标和中间元素的下标和最后元素的下

梦里梦外;/ 2022年01月23日 12:51/ 0 赞/ 265 阅读

相关二分查找（数据结构与算法）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXh

谁借莪１个温暖的怀抱￠/ 2021年12月23日 23:49/ 0 赞/ 308 阅读

相关 C++数据结构与STL--二分查找

给出数组int arr\[\]=\{-7,3,5,8,12,16,23,33,55\}; \查找target=23 ![20130725213829531][]

偏执的太偏执、/ 2021年12月16日 08:53/ 0 赞/ 253 阅读