我要招人

去企业版

首页 > 试题广场 >

二分查找-II

[编程题]二分查找-II

热度指数：190921 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请实现有重复数字的升序数组的二分查找

给定一个元素有序的（升序）长度为n的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的第一个出现的target，如果目标值存在返回下标，否则返回 -1

数据范围： $0 \le n \le 100000\$

进阶：时间复杂度 $O(logn)\$ ，空间复杂度 $O(n)\$

示例1

输入

[1,2,4,4,5],4

输出

说明

从左到右，查找到第1个为4的，下标为2，返回2

示例2

输入

[1,2,4,4,5],3

输出

-1

示例3

输入

[1,1,1,1,1],1

输出

算法知识视频讲解

数据结构和算法

发表于 2021-03-31 16:57:47

精华题解往左边逼近 public int search(int[] nums, int target) { //边界条件判断 if (nums == null || nums.length == 0) return -1; in 展开全文

宫水三叶的刷题日记

发表于 2021-08-25 15:53:08

精华题解朴素解法一个朴素的解法是直接对进行线性扫描，当第一次遇到说明找到了答案。代码： import java.util.*; public class Solution { public int search (int[] nums, int target) { in 展开全文

棒棒糖🍭201906101800876

发表于 2021-07-20 11:31:44

精华题解 NC105 二分查找-II 1. 顺序查找思路略。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 如果目标值存在返回下标，否则返回 -1 * @para 展开全文

changed.

发表于 2021-07-17 16:52:32

精华题解方法一：二分查找到指定元素后找到最左边核心思想：首先使用二分查找，寻找到一个与目标值相等的数，之后往左侧线性查找到最左边或到不等于目标值的元素核心代码： class Solution { public: int search(vector<int>& nums, 展开全文

Chiaa

发表于 2021-03-03 12:15:33

思路普通的二分法查找，需要注意题目要求从左到右，返回第一个为target的下标代码*（JAVA） import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可展开全文

小猪部落

发表于 2021-03-13 17:16:22

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 如果目标值存在返回下标，否则返回 -1 * @param nums 展开全文

子夜降晴空

发表于 2021-03-10 19:40:04

class Solution { public: int search(vector<int>& nums, int target) { return(helper(nums, target, 0, nums.size() - 1)); } 展开全文

只为刷题

发表于 2021-05-24 15:05:58

JAVA二分法的思想:思路：设置三个哨兵位置(min max mid)初始时候mid = (min +max)/2 的位置然后用被查找的对象数和mid去比较，如果大于mid，则表示对象数在mid的右侧，此时更新查找范围，把min变为mid+1 （此处用数组下标说明）如果小于mid，则表示对象数在展开全文

小陆要懂云

发表于 2021-08-04 17:27:23

auto result=equal_range(nums.begin(), nums.end(), target); if(result.first==result.second) return -1; else return result.first 展开全文

凯东

发表于 2021-03-28 20:24:14

感觉这道题题目有点问题，没有说是取出现的第一个还是最后一个，通过测试用例结果来看应该是取第一个出现的值。所以在得到匹配的值mid的时候，还需要做两个判断: 如果已经是数组第一个数据，直接返回mid的值如果不是数组第一个数据，那么前面的数如果不等于当前mid的数，返回mid即可上述均不满足的时候展开全文