首页 > 试题广场 >

二分查找-I

[编程题]二分查找-I
  • 热度指数：222399 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
请实现无重复数字的升序数组的二分查找

给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1

数据范围： ， 数组中任意值满足
进阶：时间复杂度 ，空间复杂度

示例1

输入

[-1,0,3,4,6,10,13,14],13

输出

6

说明

13 出现在nums中并且下标为 6
示例2

输入

[],3

输出

-1

说明

nums为空，返回-1
示例3

输入

[-1,0,3,4,6,10,13,14],2

输出

-1

说明

2 不存在nums中因此返回 -1

备注:
数组元素长度在[0,10000]之间
数组每个元素都在 [-9999, 9999]之间。
算法知识视频讲解
添加回答
Python3
lintoon头像 lintoon
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        left=0
        right=len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]>target:
                right=mid-1
            else:left=mid+1
        else:return -1
发表于 2024-04-07 15:55:06 回复(0)
Python3
烦恼的安哥拉兔喜欢摸鱼头像 烦恼的安哥拉兔喜欢摸鱼
class Solution:
    def search(self , nums: List[int], target: int):
        # write code here
        if target in nums:
            res = nums.index(target)
            return res
        else:
            return -1
发表于 2023-12-05 21:25:57 回复(1)
Python3
LeoAlan头像 LeoAlan 
class Solution(object):
    def search(self , nums, target):
        self.target = target
        self.nums = nums

        return self.erfen(0, len(nums)-1)

    def erfen(self, left, right):

        if left > right:
            return -1

        m = (left+right)//2

        if self.target == self.nums[m]:
            return m
        elif self.target < self.nums[m]:
            return self.erfen(left, m-1)
        else:
            return self.erfen(m+1, right)

发表于 2023-10-08 21:38:23 回复(0)
Python3
猛牛向前冲头像 猛牛向前冲 
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        left_index = 0
        right_index = len(nums) - 1
        target_index = -1
        while left_index <= right_index:
            center_index = (left_index + right_index) // 2
            center_num = nums[center_index]
            if center_num < target:
                left_index = center_index +1
            elif center_num > target:
                right_index = center_index -1
            else:
                target_index = center_index
                break
        return target_index

发表于 2023-09-26 15:01:56 回复(0)
Python3
嘿哈_MAN头像 嘿哈_MAN
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        f=-1
        left=0
        right=int(len(nums))-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]==target:
                f=mid
                break
            else:
                if nums[mid]<target:
                    left=mid+1
                if nums[mid]>target:
                    right=mid-1
        return f

发表于 2023-09-21 10:56:34 回复(0)
Python3
牛客20210711号头像 牛客20210711号 
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        left=0
        right=len(nums)-1
        while left<=right:
            middle=(left+right)//2
            if nums[middle]==target:
                return middle
            if nums[middle]>target:
                right=middle-1
            else:
                left=middle+1
        return -1

发表于 2023-09-21 10:41:10 回复(0)
Python3
米冻_头像 米冻_
好像可以用内置函数。。。
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @param target int整型
# @return int整型
#
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        if len(nums) == 0:
            return -1
        try:
            idx = nums.index(target)
        except:
            idx = -1
        return idx
发表于 2023-09-09 15:23:41 回复(0)
Python3
神马一族头像 神马一族 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        n=len(nums)
        left_index=0
        right_index=n-1
        while left_index<=right_index:
            mid_index=(left_index+right_index)//2
            if nums[mid_index]>target:
                right_index=mid_index-1
            if nums[mid_index]<target:
                left_index=mid_index+1
            if nums[mid_index]==target:
                return mid_index
        return -1

发表于 2023-08-04 11:11:14 回复(0)
Python3
ysy422头像 ysy422 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        length = len(nums)
        # 空列表
        if length == 0: return -1

        # 1个数值
        if length == 1:
            return -1 if target != nums[0] else 0

        # 多个数值    
        left = 0
        right = len(nums) - 1

        #过界
        if (nums[left] > target)&nbs***bsp;(nums[right] < target):
            return -1
        
        # 边界
        if nums[left] == target: return 0
        if nums[right] == target: return right

        # 界内
        while right - left > 1:
            # 二分
            mid = (left + right)//2

            if nums[mid] > target:
                right = mid
            elif nums[mid] < target:
                left = mid
            else:
                return mid
        return -1
如注释
发表于 2023-05-11 23:50:41 回复(0)
Python3
琵琶语头像 琵琶语 
class Solution:
    # 二分查找, 必须是升序数组。
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        l = 0
        r = len(nums) - 1
        # 从数组首尾开始, 直到两者相遇
        while l <= r:
            # 求中间值
            tgt_ind = l +int((r-l)/2)
            # 检查中间值是否等于目标值
            if nums[tgt_ind] == target:
                return tgt_ind
            # 中间值大于目标值, 表示在左区间
            if nums[tgt_ind] > target:
                r = tgt_ind - 1
            else: # 中间值小于于目标值, 表示在右区间
                l = tgt_ind + 1
        return -1

发表于 2023-04-01 18:43:17 回复(0)
Python3
xblackleopard头像 xblackleopard 
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        length = len(nums)
        left = 0
        right = length
        if length < 1:
            return -1 
        while  left <= right:
            mid = int((left + right) / 2)
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

发表于 2022-07-22 16:48:07 回复(0)
Python3
牛客178259117号头像 牛客178259117号
记下标貌似比直接切片好使
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        if len(nums) < 1:
            return -1
        left = 0
        right = len(nums) -1
        while left <= right:
            mid = int((left + right)/2)
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid -1
            elif nums[mid] < target:
                left = mid + 1
        return -1
发表于 2022-02-27 23:29:38 回复(0)
提交观点

问题信息

二分
上传者：牛客301499号
难度：
13条回答 3883浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号