首页 > 试题广场 >

二分查找-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]之间。
算法知识视频讲解
添加回答
C
徐文达头像 徐文达 
int search(int* nums, int numsLen, int target ) 
{
    int* left = nums;
    int* right = nums + numsLen - 1;
    int* middle = NULL;

    while(left <= right)
    {
        middle = left + (right - left) / 2;

        if(*middle < target)
        {
            left = middle + 1;
        }
        else if (*middle > target)
        {
            right = middle - 1;
        }
        else 
        {
            return middle - nums;
        }
    }

    //走到这里。说明没有该元素
    return -1;
}

发表于 今天 19:36:18 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
int search(int* nums, int numsLen, int target ) {
    int start=0,end=numsLen-1;
    if(!numsLen)
        return -1;
        
    while(start<=end) {
        int mid = (end+start+1)/2;
        if(target>nums[mid]) 
            start = mid+1;
        else if(target<nums[mid]) 
            end = mid-1;
        else 
            return mid;
    }
    return -1;
}

发表于 2024-03-16 08:52:40 回复(0)
C
Decoi头像 Decoi
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @param numsLen int nums数组长度
 * @param target int整型
 * @return int整型
 */
int search(int* nums, int numsLen, int target ) {
    // write code here
    int left = 0;
    int right = numsLen - 1;
    while(left <= right){
        int mid = (left + right)/2;
        if(*(nums + mid) == target)
            return mid;
        else if (*(nums + mid) > target)
            right = mid - 1;
        else
            left = mid + 1;
        }
    return -1;
}
编辑于 2023-12-15 22:59:27 回复(0)
C
唱跳Rap打篮球的_______头像 唱跳Rap打篮球的_______
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @param numsLen int nums数组长度
 * @param target int整型
 * @return int整型
 */
int search(int* nums, int numsLen, int target ) {
    int x=0,y=numsLen-1,mid=(x+y)/2;
    while(x<=y){  //二分模板
        mid=(x+y)/2;
        if(nums[mid]==target){
            return mid;
        }
        else if(*(nums+mid)<target){
            x=mid+1;
        }
        else{
            y=mid-1;
        }
    }
    return -1;
}
发表于 2023-10-06 12:52:53 回复(0)
C
快乐JY头像 快乐JY
int search(int* nums, int numsLen, int target ) {
    // write code here
    int mid=0,i;
    while(mid<=numsLen){
        i=(mid+numsLen)/2;//i表示中间数下标
        if(target==nums[i]) //先做等运算，如果一分为二直接找到就不用再做后面运算
        return i;
        else if(target<nums[i])
        numsLen=i-1;
        else
        mid=i+1;
        }
    return -1;
    }
发表于 2023-09-14 00:49:14 回复(0)
C
巴尔泽布头像 巴尔泽布 
int search(int* nums, int numsLen, int target ) {
    if (!numsLen) return -1;
    else if (numsLen == 1 && nums[0] != target) return -1;
    else {
        int pos = numsLen / 2;
        if (nums[pos] == target) return pos;
        if (nums[pos] > target) return search(nums, pos, target);
        else {
            int j = search(nums + pos + 1, numsLen - pos - 1, target);
            if(j == -1) return -1;
            else return pos + 1 + search(nums + pos + 1, numsLen - pos - 1, target);
        }
    }
}

发表于 2023-02-05 22:05:29 回复(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) return mid;
        if(nums[mid]<target) left=mid+1;
        if(nums[mid]>target) right=mid-1;
    }
    return -1;
}
发表于 2022-11-08 15:00:52 回复(0)
C
取nm名字全被取了头像 取nm名字全被取了 
int search(int* nums, int numsLen, int target ) 
{
    int min = 0,max = numsLen-1,mid = (min+max)/2;
    while(max >= min)
    {
        if(target > nums[mid])
        {
            min = mid+1;
            mid = (min+max)/2;
        }
        else if(target < nums[mid])
        {
            max = mid-1;
            mid = (min+max)/2;
        }
        else
        {
            return mid;
        }
    }
    return -1;
    // write code here
}

发表于 2022-11-04 16:35:56 回复(0)
C
牛客347719号头像 牛客347719号
int searchRange(int* nums, int start, int end, int target) {
    if (end - start < 2) {
        if (nums[start] == target) {
            return start;
        } else if (nums[end] == target) {
            return end;
        } else {
            return -1;
        }
    }
    if (nums[(start + end) /2] > target) {
        return searchRange(nums, start, (start + end) /2, target);
    } else {
        return searchRange(nums, (start + end) /2, end, target);
    }
}
int search(int* nums, int numsLen, int target ) {
    // write code here
    return searchRange(nums, 0, numsLen-1, target);
}
发表于 2022-05-29 16:34:41 回复(0)
C
牛客572130657号头像 牛客572130657号 
int search(int* nums, int numsLen, int target ) {
    if(numsLen==0)  return -1;
    int left=0,right=numsLen-1,mid;
    while(left<=right){    //当left>right时停止
        mid=(left+right)/2;
        if(nums[mid]>target) right=mid-1;
        else if(nums[mid]<target) left=mid+1;
        else  return mid;
    }
    return -1;
}


发表于 2022-05-25 22:53:29 回复(1)
C
阿金要努力头像 阿金要努力 
int search(int* nums, int numsLen, int target ) 
{
    // write code here
    int left=0;
    int right=numsLen-1;
    while(left<=right)
    {
        int mid=left+(right-left)/2;
        if(nums[mid]<target)
        {
            left=mid+1;
        }
        else if(nums[mid]>target)
        {
            right=mid-1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

发表于 2022-04-20 17:10:28 回复(1)
C
牛客786262423号头像 牛客786262423号
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @param target int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int search(int* nums, int numsLen, int target ) {
    // write code here
    int low,high,mid=0;
    low=0;
    high=numsLen-1;
    while(low<=high&&nums[mid]!=target){
        mid=(low+high)/2;
        if (nums[mid]>target){
            high=--mid;
        }
        else if(nums[mid]<target){
            low=++mid;
        }
    }
    if(low>high)
        return -1;
    else
        return mid;
}
发表于 2022-03-31 11:02:02 回复(0)
C
一个fw狗头像 一个fw狗 
int search(int* nums, int numsLen, int target ) {
    // write code here
    if(nums==NULL){
        return -1;
    }
    int mid,left=0,right=numsLen-1;
    while(left<=right){
        mid=(left+right)/2;
       if(nums[mid]<target)
            left=mid+1;
       else if(nums[mid]>target)
            right=mid-1;
       else (nums[mid]==target)
            return mid;
    }
    return -1;//在while中没有返回值则说明target在数组中无法找到返回-1
}

发表于 2022-03-23 19:05:19 回复(0)
C
Chromium丶头像 Chromium丶 
int search(int* nums, int numsLen, int target ) {
    int min = 0,mid,max = numsLen;
    while(min<=max){
        mid = (max+min)/2;
        if(nums[mid] == target) return mid;
        if(nums[mid]>target) max = mid-1;
        else min = mid+1;
    }
    return -1;
}

发表于 2022-03-16 15:50:02 回复(0)
C
呸，看见你就开心头像 呸，看见你就开心
int search(int* nums, int numsLen, int target ) {
    // write code here
    if(numsLen==0){
        return -1;
    }
    int i=0,j=numsLen-1,mid;
    int f;
    while(i<j){
        mid = (i+j)/2;
        if(nums[mid] == target){
            f = mid;
            break;
        }else if(nums[mid] > target){
            j = mid-1;
        }else{
            i = mid+1;
        }
    }
    if(i==j && nums[i]!=target){
        return -1;
    }else if(i==j && nums[i]==target){
        return i;
    }else{
        return f;
    }
}
发表于 2022-03-12 17:00:44 回复(1)
C
热爱i头像 热爱i
int search(int* nums, int numsLen, int target ) {
    // write code here
    int low = 0,high=numsLen-1;
    while (low<=high){
        int mid = (low+high)/2;
        if (nums[mid]==target)
            return mid;
        else if (nums[mid]<target){
            low = mid+1;
        } else if (nums[mid] > target){
            high = mid-1;
        }
    }
    return -1;
}
发表于 2022-02-26 22:00:57 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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