【LintCode 简单】14. 二分查找

﹏ヽ暗。殇╰゛Y 2022-06-01 07:45 140阅读 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 条评论，140人围观）

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

相关阅读

相关二分查找的简单实现

> 简单记录了一下二分查找的实现文章目录前言一、二分查找是什么？二、代码实现总结 -------------------- 前言这天，六花来

小灰灰/ 2024年03月24日 10:56/ 0 赞/ 52 阅读

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

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

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

相关 lintcode:二分查找

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关二分查找

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

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

相关查找——二分查找

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

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

相关 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 赞/ 280 阅读