【LintCode 简单】14. 二分查找

﹏ヽ暗。殇╰゛Y 2022-06-01 07:45 134阅读 0赞

1.问题描述：

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

2.样例：

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

3.代码：

class Solution:
        # @param nums: The integer array
        # @param target: Target number to find
        # @return the first position of target in nums, position start from 0 
        def binarySearch(self, nums, target):
            # write your code here
            length=len(nums)
            start=0
            end=length
            mid=(end-start)/2
            while start<=end:
                if nums[mid]<target:
                    start=mid+1
                    mid=(end+start)/2
                elif nums[mid]>target:
                    end=mid-1
                    mid=(end-start)/2
                else:
                    while nums[mid]==target:
                        mid-=1
                    return mid+1
            return -1

本题是二分查找内容，但是因为测试数组中存在相同的数，需要返回第一个。所以，在二分查找的基础上增加了一些内容。

对于二分查找要注意，当大于或小于时，移动start或end标示：start = mid+1 或 end = mid-1

当找到target目标值时，通过不断mid-1 来取得第一个target值。

发表评论取消回复

表情：

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

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

相关阅读

相关最简单的算法- 二分查找

java代码 / Created by fupeng on 2017/1/11. / public class binarySearch {

以你之姓@/ 2022年08月21日 10:50/ 0 赞/ 147 阅读

相关 lintcode:二分查找

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

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

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

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

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

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

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

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

相关【LintCode 简单】13. 字符串查找

1.问题描述：对于一个给定的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果

今天药忘吃喽~/ 2022年06月01日 00:09/ 0 赞/ 231 阅读

相关二分查找有这么简单?

题目一 > 给定一个有序（非降序）数组A，求任意一个i使得A\[i\]等于key，不存在则返回-1 这个是最原始的二分查找题目，利用数组的有序特性，拆半查找，使得查找时

布满荆棘的人生/ 2022年05月19日 02:53/ 0 赞/ 151 阅读

相关二分查找

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

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

相关查找——二分查找

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

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

相关二分查找

1 二分查找　　二分查找是一个基础的算法，也是面试中常考的一个知识点。二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果

本是古典何须时尚/ 2022年03月08日 10:28/ 0 赞/ 620 阅读

相关 LintCode : 14. First Position of Target 二分查找，重复数字第一次出现下标

试题 For a given sorted array (ascending order) and a target number, find the first inde

布满荆棘的人生/ 2021年06月24日 16:10/ 0 赞/ 274 阅读