首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >14. 二分查找

14. 二分查找

作者头像
和蔼的zhxing
发布2018-09-04 13:19:21
3440
发布2018-09-04 13:19:21
举报

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1。 如:在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3,返回2。 思路:二分查找是基本功,可以写迭代也可以写while循环,目前还是习惯写while循环一些,但是这里的要求和一般的二分查找还不太一样,主要的原因是题目要求查找出第一个,也就是即使找到了一个,也不能立即返回,需要找到第一个才行,我想了一下,有一个思路:找到了把结果赋值给一个变量,然后end更新为mid-1(因为第一个肯定比这个索引小,如果存在的话),一直把所有的二分查找都找完,返回最新的一个查找的结果就是要求的第一个的索引:

int binarySearch(vector<int> &array, int target) {
        auto beg=array.begin();
        auto end=array.end()-1;
        int res=-1;   //如果这个res最后还是-1的话,就说明没有找到。
        while(beg<=end)
        {
            auto mid=beg+(end-beg)/2;
            if(*mid==target)
            {
            res=mid-array.begin();    //这里是找到了,但不能保证是第一个
            end=mid-1;    //mid仍然更新。
            }
            if(*mid<target)
            beg=mid+1;
            if(*mid>target)
            end=mid-1;
           
        }
        if(res!=-1)
        return res;
        // write your code here
        return -1;
    }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017.11.15 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档