二分查找

已知一个排序数组A,如A= [-1,2,5,20,90,100,207,800] 另外一个乱序数组B,如B =[50,90,3,-1,207,80] 求B中的任意某个元素,是否在A中出现,结果存储在数组C中,出现用1代表,未出现用0代表,如,C = [0,1,0,1,1,0]。

最暴力的方法: o(n2) 折半查找: 对于某个元素是(logn),如果有那个元素就是(nlogn)。

std::vector<int> search_array(std::vector<int> & sort_array, std::vector<int> &random_array){
}

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

递归版本:

#include<vector>
bool binary_search(std::vector<int> &sort_array, int begin, int end, int target){
    if(begin > end ){
        return false;// 区间不存在!
    }
    int mid = (begin + end) / 2  ;//找中点
    if(target == sort_array[mid]){
        return true;
    }
    else if( target == sort_array[mid]){//在左区间查找 
        return binary_search(sort_array, begin, mid-1,target);

    }
    else if(){
        return binary_search(sort_array, mid +1, end, target);
    }
}

循环实现:

bool binary_search(std::vector<int> &sort_array, int target){
    int begin = 0;
    int end = sort_array.size() -1;
    while(begin <= end){
        int mid =(begin + end)/ 2;
        if(target == sort_array[mid]){
            return true;
        }
        else if(target < sort_array[mid]){
            end = mid -1;
        }
        else if(target > sort_array[mid]){
            begin = mid +1;
        }
    }
    return false;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏海天一树

小朋友学数据结构(6):折半查找法

假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键...

11910
来自专栏数据结构与算法

BZOJ4355: Play with sequence(吉司机线段树)

这题最坑的地方在于对于操作1,$C >= 0$, 操作2中需要对0取max,$a[i] >= 0$,这不就是统计最小值出现的次数么??

21020
来自专栏CaiRui

Mysql-7-mysql函数

1.数学函数   用来处理数值数据方面的运算,主要的数学函数有:绝对值函数,三角函数,对数函数,随机函数。使用数学函数过程中,如果有错误产生,该函数会返回nul...

21570
来自专栏恰童鞋骚年

Hadoop学习笔记—11.MapReduce中的排序和分组

  从上图中可以清楚地看出,在Step1.4也就是第四步中,需要对不同分区中的数据进行排序和分组,默认情况下,是按照key进行排序和分组。

12820
来自专栏NetCore

解读C#中的正则表达式

 多少年来,许多的编程语言和工具都包含对正则表达式的支持,.NET基础类库中包含有一个名字空间和一系列可以充分发挥规则表达式威力的类,而且它们也都与未...

24670
来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - 关联对象实现原理

21360
来自专栏Ryan Miao

MongoDB-基础-条件操作符

1.一些解释 less than         :  比..少  lt greater than      :  比..多  gt equals       ...

31160
来自专栏康怀帅的专栏

Redis hash 类型

赋值 hset hash1 key1 12 hget hash1 key1 hgetall hash1 # 获取某个哈希表...

36660
来自专栏杨建荣的学习笔记

关于oracle中的sql数据类型(r3笔记第59天)

数据类型对于每一种编程语言而言都是数据存储的基础,对于编程语言的实现功能而言也是一个标尺,有些编程语言可能数据类型很丰富,比如java,c,在数据计算方面的支持...

29340
来自专栏跟着阿笨一起玩NET

SQL Server数据库获取TEXT字段的内容长度的方法

SQL Server数据库如何获取TEXT字段的内容长度呢?本文我们就来介绍一下SQL Server数据库如何获取TEXT字段的内容长度的方法,是通过DATA...

23030

扫码关注云+社区

领取腾讯云代金券