首页 > 试题广场 >

二分查找-I

[编程题]二分查找-I

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

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

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

数据范围： $0 \le len(nums) \le 2\times10^5$ ，数组中任意值满足 $|val| \le 10^9$

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

示例1

输入

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

输出

说明

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]之间。

算法知识视频讲解

牛客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 回复(2)

C++

潘睿

int search(vector<int>& nums, int target) {
vector<int>::iterator iter = lower_bound(nums.begin(), nums.end(), target);
return ((iter == nums.end()) || (*iter != target)) ? -1 : iter - nums.begin();
}

发表于 2022-10-12 20:26:28 回复(0)

Java

牛客用户007

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        if (nums.length == 0) return -1;

        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (target == nums[mid]) return mid;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }
}

发表于 2022-08-25 14:22:11 回复(0)

Java

M_许洛

     public int search (int[] nums, int target){
        return search(nums,target,0,nums.length-1);
    }

    public int search (int[] nums, int target,int left,int right) {
        // write code here
        if(left>right ){
            return -1;
        }

        int middle = (left+right)/2;
        
        if(nums[middle]==target){
            return middle;
        }else if(nums[middle] < target){
            return search(nums,target,middle+1,right);
        }else{
            return search(nums,target,left,middle-1);
        }
        
    }

二分递归的思路很好记忆和书写。

等于出来，大于下面一半找，小于上面一半找
注意数组越界判断和边界+-1操作

发表于 2022-08-14 14:07:17 回复(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 回复(2)

JavaScript Node

意思丶

我怎么一步就出来了

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param target int整型 
 * @return int整型
 */
function search( nums ,  target ) {
    // write code here
    return nums.indexOf(target)
}
module.exports = {
    search : search
};

发表于 2022-12-05 15:33:08 回复(2)

Python3

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)

来个offer叭！

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

发表于 2022-07-21 10:36:33 回复(0)

Python 3

Joy_9

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        left=0
        right=len(nums)-1
        while left<=right:
            mid=(right+left)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]>target:
                right=mid-1
            elif nums[mid]<target:
                left=mid+1
        return -1

发表于 2022-01-09 04:02:41 回复(0)

C++

ThinkLikeAnElectron

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        int left=0, right= nums.size();
        while(left<right){
            int mid = (left+right)>>1;
            if(nums[mid]==target){
                return mid;
            }
            if(nums[mid]>target){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return -1;
    }
};

关于while里面的条件想分享一些我的见解：

1. 当right的起始值为len-1时必须采用left<=right，因为右边界时必须访问到的，此时修改left和right的地方必须都对mid做递增或递减；

2. 当right起始值为len时，while条件就可以为left<right，修改right的地方也变成了直接用mid，因为此时右边界是不可访问的

发表于 2024-06-27 18:07:40 回复(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)

Javascript

WeiChen666

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param target int整型 
 * @return int整型
 */
function search( nums ,  target ) {
    // write code here
     let i = 0;
    while (i < nums.length) {
        if (nums[i] == target) {
            return i;
        }
        i++;
    }
    return -1;
}
module.exports = {
    search : search
};

发表于 2022-09-01 12:47:59 回复(2)

C++

牛客653507322号

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @param target int整型
* @return int整型
*/
int search(vector<int>& nums, int target) {
// write code here
if(nums.empty()) return -1;
int n=nums.size();
int i=0,j=n-1;
if(nums[i]==target) return i;
if(nums[j]==target) return j;
if(i==j && nums[i]==target) return 0;
if(i==j && nums[i]!=target) return -1;
while(i<j){
if(nums[(i+j)/2]==target) return (i+j)/2;
if(target>nums[(i+j)/2]){
i=(i+j)/2;
}
if(target<nums[(i+j)/2]){
j=(i+j)/2;
}
if((j-i)==1) break;
}
return -1;
}
};

发表于 2022-08-24 14:14:40 回复(0)

Spectre_

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        int start = 0, end = nums.size() - 1, middle;
        while (start <= end) {
            middle = start + ((end - start) >> 1);
            if (nums[middle] == target) return middle;
            else if (nums[middle] < target) start = middle + 1;
            else end = middle - 1;
        }
        return -1;
    }
};

发表于 2021-09-07 22:23:59 回复(0)

Java

渴望wlb的可乐很喜欢吃蛋

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        int begin = 0;
        int end = nums.length-1;
        int mid = 0;
        while(begin<=end){
            mid = (begin+end)/2;
            if(target == nums[mid]){
                return mid;
            }else if (target<nums[mid]){
                end = mid -1;
            }else if (target>nums[mid]){
                begin = mid + 1;
            }
        }
    return -1;
    }
}

发表于 2023-06-30 18:31:41 回复(0)

Java

GoIn

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        if(nums.length==0){
            return -1;
        }
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid]==target){
                return mid;
            }
            else if(nums[mid]<target){
                left = mid+1;
            }
            else if(nums[mid]>target){
                right = mid-1;
            }
        }
        return -1;
    }
}

发表于 2023-01-11 10:16:42 回复(0)

牛客357419673号

int search(int* nums, int numsLen, int target ) {

// write code here

int sidx = 0, eidx = numsLen - 1;

while (sidx <= eidx) {

int mid = (sidx + eidx) / 2;

if (nums[mid] < target) {

sidx = mid + 1;

} else if (nums[mid] > target) {

eidx = mid - 1;

} else {

return mid;

}

return -1;

}

发表于 2025-01-10 20:33:30 回复(0)

StellarVibes

if(nums[mid]>target)

{

left = mid;

}

发表于 2024-12-07 17:33:22 回复(1)

Java

牛客66837482号

public int search (int[] nums, int target) {

// write code here

int i = 0;

int j = nums.length - 1;

while(i<=j){

int m = (i + j) >>> 1;

if (target < nums[m]) {

j = m - 1;

}else if(nums[m]<target){

i=m+1;

} else {

return m;

}

return -1;

}

发表于 2024-11-20 17:29:49 回复(0)

Java

PeterLee6688

主要是理解(x + y) /2 等于开始计算位置到计算末尾位置的中间位置

    public int search (int[] nums, int target) {
        // write code here
        int len = nums.length;
        if (len == 0) {
            return -1;
        }
        int begin = 0 ; // 开始位置
        int end = len - 1; // 结束位置
        int mid = 0; // 中间位置
        while (begin <= end) {
            mid = (begin + end) / 2; 
            if (target == nums[mid]) {
                return mid;
            } else if (target < nums[mid]) {
                end = mid - 1;
            } else if (target > nums[mid]) {
                begin = mid + 1;
            }
        }
        return -1;
    }

发表于 2024-05-15 22:02:49 回复(0)

提交观点

问题信息

二分

上传者：牛客301499号

难度：

257条回答 527收藏 6243浏览

通过挑战的用户

查看代码

TV体育

2023-03-05 10:21:37
随机昵称都有什...

2023-02-17 18:15:42
His步步

2023-01-19 13:25:18
lightzc

2022-12-25 00:28:03
Echo_paul

2022-11-02 22:53:01

二分查找-I

输入

输出

说明

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题