OJ lintcode 二分查找

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1。
您在真实的面试中是否遇到过这个题?
Yes
样例
在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3,返回2。

class Solution {
public:
    /**
     * 这个题不难, 很常见,但是有点卡顿
     * 问题:
     * 1. vector 是可以按照下标访问的,下标的顺序是 0~size()-1
     * 2.对于递归函数的设计思路,一定要想清楚它的终止条件
     * 
     * 终止:
     *  1. 如果begin,和end挨在一起,即(end-begin<=1),
     *          1. 但是还没有找到 end和begin都不是target  返回-1
     *          2. end 和begin 有一个是 target  ,返回下标
     *  2. mid=(end+begin)/2  a[mid]==target  
     *          看一下mid前面的元素是不是target
     *          然后返回下标
     * 
     * @param nums: The integer array.
     * @param target: Target number to find.
     * @return: The first position of target. Position starts from 0. 
     */
    int bin_search(vector<int> &a,int begin,int end,int target){
        if(end-begin<=1){
            if(a[begin]==target){
                return begin;
            }
            if(a[end]==target){
                return end;
            }
            //没有命中
            return -1;
        }
        else{
            int mid=(begin+end)/2;
            if((a[mid])==target){
                //命中
                //找到最前面的元素的下标
                while(a[mid]==target){
                    mid--;
                }
                mid++;
                return mid;
            }
            else{
                if((a[mid])<target){
                    bin_search(a,mid,end,target);
                }
                else
                {
                    bin_search(a,begin,mid,target);
                }
            }
        }
    }
    int binarySearch(vector<int> &array, int target) {
        // write your code here
        int begin=0;
        int end=array.size()-1;
        return bin_search(array,begin,end,target);

    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 版权声明:本文为博主原创文章,未经博主允许不得转载。 难度:容易 要求: 给定一个排序的整数数组(升序)和一个要查...
    柒黍阅读 431评论 0 0
  • 题目 描述 给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target...
    悠扬前奏阅读 230评论 0 0
  • 题目前的数字是对应的lintcode的题目序号 14.二分查找 给定一个排序的整数数组(升序)和一个要查找的整数t...
    mytac阅读 703评论 1 2
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,767评论 0 33
  • 晚上10点,萱萱要喝奶。今天跟奶奶睡,萱萱扭来扭去,小撒娇着,一定要夜里喝奶才睡觉。奶奶疼爱都来不及,哪里会拒绝,...
    清风浅浅阅读 463评论 5 1