首页 > 试题广场 >

二分查找-II

[编程题]二分查找-II
  • 热度指数：191838 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
请实现有重复数字的升序数组的二分查找
给定一个 元素有序的（升序）长度为n的整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的第一个出现的target，如果目标值存在返回下标，否则返回 -1

数据范围：
进阶：时间复杂度，空间复杂度
示例1

输入

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

输出

2

说明

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

输入

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

输出

-1
示例3

输入

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

输出

0
算法知识视频讲解
添加回答
C
80后大叔头像 80后大叔

在普通二分查找基础上，增加一个往左寻找第一个出现的位置即可

int search(int* nums, int numsLen, int target ) {
    // write code here
    if(numsLen==0) return -1;
    int left=0, right=numsLen-1;
    while(left<=right) {
        int mid = left+(right-left)/2;
        if(nums[mid]==target) {
            while(nums[mid]==target) {
                mid--;
            }
            return mid+1;
        }
        if(nums[mid]<target) left=mid+1;
        if(nums[mid]>target) right=mid-1;
    }
    return -1;
}
发表于 2022-11-08 15:59:51 回复(0)
C
拓跋友友头像 拓跋友友 
int search(int* nums, int numsLen, int target )
{
    int zuo=0;
    int you=numsLen-1;
    int zhong=0;
    while(zuo<=you)
    {
        zhong=(zuo+you)/2;
        if(nums[zhong]<target)
        {
            zuo=zhong+1;
        }
        else if(nums[zhong]>target) 
        {
            you=zhong-1;
        }
        else
        {
            int t=zuo;
            while(nums[t]!=target) 
            {
                t++;
            }
            return t;
            break;
        }
    }
    return -1;
}

发表于 2021-12-18 23:08:07 回复(0)
C
xiaolock883头像 xiaolock883
首先定义一个left 一个right。left初始化为0，right初始化为numslen-1（因为数组的下标是实际顺序-1）。
循环条件为left<=right。当nums[I]<=target时，目标值在右侧，将left改为I+1，>=则相反。
最后找到目标值时需要向前遍历，判断前几个值是否为同样的值，由于题目要求，需要返回第一个目标值，因此循环到nums[j-1]!=target结束。
需要注意的是，这时不能使用nums[j--]，因为这样的话会提前改变j的值，最好先判断num[j-1]是否满足条件，如果满足条件了，再进行j--，最后返回下标j。
代码如下： 
nt search(int* nums, int numsLen, int target ) {
    // write code here
    int i = 0;
    int right = numsLen-1;
    int left = 0;
    int j = 0;
    while(left<=right)
    {
        i = (right+left)/2;
        if(nums[i]<target)
        {
            left = i+1;
        }
        else if(nums[i]>target)
        {
            right = i-1;
        }
        else
        {
            int j = i;
            while(nums[j-1] == target)
            {
                j--;
            }
        return j;
        }
    }
    return -1;
}

发表于 2021-12-01 15:34:37 回复(0)
C
牛客176196015号头像 牛客176196015号
int search(int* nums, int numsLen, int target ) {
    // write code here
    int start=0;
    int end= numsLen-1;
    while(start<=end)
    {
        int mid=(start+end)/2;
        if(nums[mid]==target)
        {
            while(nums[mid-1]==nums[mid])
                mid--;
                return mid;
        }
        if(nums[mid]<target)
            start=mid+1;
        else
            end=mid-1;
    }
    return -1;
}
发表于 2021-08-27 17:59:27 回复(0)
C
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
int cond(int* nums, int mid, int target) {
  return *(nums + mid) >= target;
}

int binary_search(int* nums, int numsSize, int target, int (*cond) (int*, int, int)) {
  int l = 0, r = numsSize, m;
  while (l < r) {
    m = l + ((r - l) >> 1);
    if (cond(nums, m, target)) r = m;
    else l = m + 1;
  }
  return l;
}

int search(int* nums, int numsLen, int target) {
  int index = binary_search(nums, numsLen, target, cond);
  if (index == numsLen || *(nums + index) > target)
    return -1;
  return index;
}

发表于 2021-08-02 19:51:07 回复(0)
C
Zzy-__y头像 Zzy-__y 
int search(int* nums, int numsLen, int target ) 
{
    int i=0;
    for(i=0;i<numsLen;i++)
        if(*(nums++)==target)
            return i;
    return -1;
}
不一定要真使用二分，使用指针也是一个不错的选择

发表于 2021-07-28 21:24:08 回复(2)
提交观点

问题信息

二分
难度：
9条回答 7486浏览

热门推荐

通过挑战的用户

查看代码

相关试题

二分查找-II

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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