lintcode:二分查找

Love The Way You Lie 2022-07-17 04:08 162阅读 0赞

**二分查找**  
[lintcode二分查找][lintcode]

> 给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。  
> 样例  
> 在数组 \[1, 2, 3, 3, 4, 5, 10\] 中二分查找3，返回2。

class Solution {
    public:
        /**
         * @param nums: The integer array.
         * @param target: Target number to find.
         * @return: The first position of target. Position starts from 0. 
         */
        int binarySearch(vector<int> &array, int target) {
            // write your code here
            long l,r;
            l=0; r=array.size();
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(array[mid]==target)
                {
                    while(mid>0 && array[mid-1]==target && mid--)//这块其实可以优化，因为可能连续的数字很//多，有兴趣的童鞋可以自己写写看
                        NULL;
                    return mid;
                }
                else if(array[mid]>target)
                    r=mid-1;
                else if(array[mid]<target)
                    l=mid+1;
            }
            return -1;
        }
    };

[lintcode]: http://www.lintcode.com/zh-cn/problem/first-position-of-target/

发表评论取消回复

表情：

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

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

相关阅读

相关二分查找

二分查找可以说是在经典不过的查找算法了，比如JAVA的库函数里，就有相应的代码实例。如下写出两个版本的二分查找，非递归和递归的非递归的 public int bi

系统管理员/ 2022年08月06日 16:24/ 0 赞/ 53 阅读

相关 lintcode:二分查找

二分查找 [lintcode二分查找][lintcode] > 给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一

Love The Way You Lie/ 2022年07月17日 04:08/ 0 赞/ 163 阅读

相关【LintCode 简单】14. 二分查找

1.问题描述：给定一个排序的整数数组（升序）和一个要查找的整数`target`，用`O(logn)`的时间查找到target第一次出现的下标（从0开始），如果target不

﹏ヽ暗。殇╰゛Y/ 2022年06月01日 07:45/ 0 赞/ 153 阅读

相关【LintCode 简单】457. 经典二分查找问题

1.问题描述：在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回-1。 2.样例：给出数组 `[1, 2, 2, 4, 5, 5]`.

Bertha 。/ 2022年06月01日 04:53/ 0 赞/ 173 阅读

相关二分查找

//二分查找 /\ 递归算法 int searchB1(int A\[\], int low, int high, int data); 非递归算法 int

绝地灬酷狼/ 2022年05月12日 01:40/ 0 赞/ 43 阅读

相关二分查找

/ 有序数组递归二分查找，定位值的下标 @param arr 目标数组 @param start 起始下标

喜欢ヅ旅行/ 2022年04月06日 14:22/ 0 赞/ 321 阅读

相关查找——二分查找

基本思想二分查找是建立在有序顺序表基础上的！步骤如下： 1. 将表中间位置记录的关键字与给定K值进行比较，若两者相等，则查找成功。 2.

蔚落/ 2022年03月27日 03:46/ 0 赞/ 375 阅读

相关二分查找

二分查找（先排序） typedef struct LNode List; struct LNode{ ElemenType Data[MAXSIZ

爱被打了一巴掌/ 2022年02月02日 17:13/ 0 赞/ 124 阅读

相关二分查找

int search2( int array\[\], int n, int v) \{ int left, right, middle;

心已赠人/ 2021年12月20日 16:07/ 0 赞/ 123 阅读

相关二分查找

二分查找二分查找是一个比较简单的算法，用 C++ 语言实现如下： template <typename T> int binary_search(

ゞ浴缸里的玫瑰/ 2021年12月13日 03:57/ 0 赞/ 185 阅读