二分查找

题意

给定一个排序的整数数组(升序)和一个要查找的整数 target,用 O(logn) 的时间查找到 target 第一次出现的下标(从 0 开始),如果 target 不存在于数组中,返回 -1

样例

在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找 3,返回 2

思路

本题的要点是查找第一次出现的位置,所以当 nums[mid] == target 时,应该将这个 mid 值赋值给 end,这样才能保证查找到的是第一个。

代码实现

class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                end = mid;
            } else if(nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        
        if (nums[end] == target) {
            return end;
        }
        
        return -1;
    }
}

原题地址

LintCode:二分查找

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

第十六天 常用API-Date&DateFormat&Calender&System&Math&基本类型包装类&正则【悟空教程】

第十六天 常用API-Date&DateFormat&Calender&System&Math&基本类型包装类&简单正则表达式【悟空教程】

972
来自专栏Android群英传

深入Java源码解析容器类List、Set、Map

1813
来自专栏个人分享

栈的压入、弹出序列

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序...

862
来自专栏向治洪

java 之容器

在Java中,我们想要保存对象可以使用很多种手段。我们之前了解过的数组就是其中之一。但是数组具有固定的尺寸,而通常来说,程序总是在运行时根据条件来创建对象,我们...

2158
来自专栏用户2442861的专栏

Java中如何遍历Map对象的4种方法

既然java中的所有map都实现了Map接口,以下方法适用于任何map实现(HashMap, TreeMap, LinkedHashMap, Hashtabl...

891
来自专栏武培轩的专栏

剑指Offer-和为S的两个数字

题目描述 输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。 输出描述: 对应每...

3214
来自专栏云霄雨霁

查找----基于有序数组

1560
来自专栏章鱼的慢慢技术路

顺序表示的线性表——顺序表

2164
来自专栏Python爬虫与数据挖掘

浅谈Python内置对象类型——数字篇(附py2和py3的区别之一)

Python是一门面向对象的编程设计语言,程序中每一样东西都可以视为一个对象。Python内置对象可以分为简单类型和容器类型,简单类型主要是数值...

1012
来自专栏Linyb极客之路

JAVA常用API整理

提供sin, cos, tan, exp, log, log10 等类方法,PI和E等类字段

2564

扫码关注云+社区