首页 > 试题广场 >

二分查找-I

[编程题]二分查找-I
  • 热度指数:215533 时间限制: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]之间。
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)
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)
    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)
     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. 等于出来,大于下面一半找,小于上面一半找
  2. 注意数组越界判断和边界+-1操作
发表于 2022-08-14 14:07:17 回复(0)
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)
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @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)
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)
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)
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)
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)
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)
我怎么一步就出来了
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @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 回复(0)
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)
function search( nums ,  target ) {
    // write code here
    let left=0
    let right=nums.length-1
    while(left<=right){
        const mid=(left+right)>>1  //这相当于Math.floor((left+right)/2)
        if(nums[mid]==target){
            return mid
        }
        if(nums[mid]>target){
            right=mid-1
        }else{
            left=mid+1
        }
    }
    return -1
}
module.exports = {
    search : search
};
发表于 2024-01-13 23:32:58 回复(0)
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 回复(0)
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 len = nums.length;
        int left = 0;
        int right = len - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = (mid > left) ? mid : left + 1;
            } else {
                right = (mid < right) ? mid : right - 1;
            }
        }

        return -1;
    }
}

发表于 2023-11-29 22:04:22 回复(0)
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 *
 * @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)
自己写的时间复杂度不过关哈哈,还是
int search(int* nums, int numsLen, int target ) {
    // write code here
    if(!nums||!numsLen)
    {
        return -1;
    }
    int beg=0;
    int end=numsLen-1;
    int mid;
    while (beg<=end) 
    {
        mid=(beg+end)/2;
        if(target==nums[mid])
        {
            return mid;
        }
        else if(target>nums[mid])
        {
            beg=mid+1;
        }
        else 
        {
            end=mid-1;
        }
    }
    return -1;
/*
    //时间复杂度不过关
     int beg=0;
     int end=numsLen-1;
     while(target!=nums[(beg+end)/2])
     {
        if(beg==end)
        {
            return -1;
        }
        if(target<nums[(beg+end)/2])
        {
            end=(beg+end)/2-1;
        }
        else 
        {
            beg=(beg+end)/2+1;
        }
        
     }

     return (beg+end)/2;
*/
}

大家都用比较好
发表于 2023-09-10 16:51:25 回复(1)
好像可以用内置函数。。。
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @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)
int search1(vector<int>& nums,int low,int high,int target){
       
        while(low<=high){
        int mid=(low+high)/2;
        if(target==nums[mid])return mid;
        if(target>nums[mid]){low=mid+1;search1( nums, low, high,target);}
        if(target<nums[mid]){high=mid-1;search1( nums, low, high,target);}
        }
        return -1;
    }
    int search(vector<int>& nums, int target) {
        // write code here
       
        return search1( nums,0,nums.size()-1, target);//一定注意high的值是nums.size()-1
    }
发表于 2023-08-19 18:43:22 回复(1)