Nc105-二分查找-II

小灰灰 2023-10-04 16:41 22阅读 0赞

### 描述 ###

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

给定一个 元素有序的（升序）整型数组 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

代码：

int search(int* nums, int numsLen, int target ) {
        // write code here
    
           int left=0,right=numsLen-1;
           while(right>=left){
               int mid=(left+right)/2;
               if(nums[mid]==target){
                   while(nums[mid-1]==target){
                       mid--;
                   }  
                   return mid;
               }
               else if(nums[mid]>target){
                   right=mid-1;
               }
               else{
                   left=mid+1;
               }
           }
        
        return -1;
    }

递归解法：

int search(int* nums, int numsLen, int target ) {
          return erfen(nums,0, numsLen-1,target);
    }
    
    
    int erfen(int *num,int left,int right,int target){
         int mid;
         if(right>=left){
            mid=(right+left)/2;
            if(num[mid]==target){
                while(num[mid-1]==target){
                    mid--;
                }
                return mid;
            }
            else if(num[mid]>target){
               right=mid-1;
                return erfen(num,left,right,target); 
            }
            else{
                left=mid+1;
                return erfen(num,left,right,target);
            }
         }
        return -1;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 Nc105-二分查找-II

描述请实现有重复数字的升序数组的二分查找给定一个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的第一个出现的ta

小灰灰/ 2023年10月04日 16:41/ 0 赞/ 23 阅读

相关二分查找-II（C++牛客网）

解题思路：（1）二分查找，先左原则 class Solution { public: / 代码中的类名、方法名、参数名

喜欢ヅ旅行/ 2022年11月16日 05:50/ 0 赞/ 163 阅读

相关 NC160 二分查找-I和NC105 二分查找-II

两个都是按升序排好的数组，区别在于NC105可能会有重复，需要找出的是target第一次出现时的index，只需要第一次找到以后再继续往左找即可。 NC160 二分查找-I

桃扇骨/ 2022年09月16日 08:41/ 0 赞/ 139 阅读

相关二分查找

二分查找可以说是在经典不过的查找算法了，比如JAVA的库函数里，就有相应的代码实例。如下写出两个版本的二分查找，非递归和递归的非递归的 public int bi

系统管理员/ 2022年08月06日 16:24/ 0 赞/ 55 阅读

相关二分查找

//二分查找 /\ 递归算法 int searchB1(int A\[\], int low, int high, int data); 非递归算法 int

绝地灬酷狼/ 2022年05月12日 01:40/ 0 赞/ 45 阅读

相关二分查找

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

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

相关查找——二分查找

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

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

相关二分查找

二分查找（先排序） typedef struct LNode List; struct LNode{ ElemenType Data[MAXSIZ

爱被打了一巴掌/ 2022年02月02日 17:13/ 0 赞/ 126 阅读

相关二分查找

int search2( int array\[\], int n, int v) \{ int left, right, middle;

心已赠人/ 2021年12月20日 16:07/ 0 赞/ 125 阅读

相关二分查找

二分查找二分查找是一个比较简单的算法，用 C++ 语言实现如下： template <typename T> int binary_search(

ゞ浴缸里的玫瑰/ 2021年12月13日 03:57/ 0 赞/ 188 阅读