首页 > 试题广场 >

二分查找-I

[编程题]二分查找-I

热度指数：305405 时间限制：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]之间。

算法知识视频讲解

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

柯达柯达鸭

//大佬帮忙修改，测试用例只能够通过一半

import java.util.*;

public class Solution {

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

int n_l=nums.length;

//为空情况

if (n_l==0) return -1;

//存在情况

else{

int l=0;

int r=n_l;

int m=(l+r)/2;

while(target!=nums[m]){

m=(l+r)/2;

if(nums[m]>target) r=m;

else if(nums[m]<target) l=m;

else if(nums[m]==target) return m;//存在目标值

//数组中不存在

else if(nums[m] != target | nums[m+1] != target | nums[m-1] != target) return -1; break;

}

//不存在的情况

return -1;

}

发表于 2024-09-20 11:23:32 回复(0)

Java

美味手擀面

看我递归解决：

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

    public int search(int[] nums,int target,int left,int right){
        if(left == right || left == right-1){ //边界处理
            if(nums[left] == target){
                return left;
            }else if(nums[right] == target){
                return right;
            }else {
                return -1;
            }
        }
        int mid = (left + right) / 2;
        if(nums[mid] == target){
            return mid;
        }else if(nums[mid] < target){
            return search(nums,target,mid,right);
        }else if(nums[mid] > target){
            return search(nums,target,left, mid);
        }
        return -1;
    }

发表于 2024-08-23 15:21:51 回复(0)

Java

牛客348570162号

public int search (int[] nums, int target) {
        int start_index = 0;
        int end_index = nums.length-1;
        while(start_index <= end_index){
            int mid_index = (start_index + end_index)/2;
            if(nums[mid_index] == target){
                return mid_index;
            }
            if(nums[mid_index] < target){
                start_index = mid_index +1;
            }else{
                end_index = mid_index - 1;
            }
        }
        return -1;
    }

发表于 2024-08-20 14:07:17 回复(0)

Java

人间水长东

import java.util.*;


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

        // 算法的时间复杂度O(logN)，额外空间复杂度O(1)

        // 1.定义左边界l和右边界r
        int l = 0;
        int r = nums.length - 1;
        int mid = 0;

        while (l <= r) {
            // 2.循环二分查找
            // 2.1 先计算中间索引mid
            mid = (l + r) / 2;
            if (target == nums[mid]) {
                // 2.2 若mid命中target，则返回mid
                return mid;
            } else if (target < nums[mid]) {
                // 2.3 若target比mid的元素小，则收缩右边界r
                r = mid - 1;
            } else {
                // 2.4 若target比mid的元素大，则收缩左边界l
                l = mid + 1;
            }
        }

        // 3.若循环结束仍没有返回，说明target不在nums中，返回-1
        return -1;
    }
}

发表于 2024-07-27 17:41:26 回复(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)

Java

你好，侦探先生

import java.util.*;


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

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

编辑于 2024-04-01 16:25:26 回复(0)

Java

追风C功

    public int search (int[] nums, int target) {
        int result = 0;
        for (int num : nums) {
            if (target == num) {
                return result;
            } else {
                result++;
            }
        }
        return -1;
    }

发表于 2024-02-28 01:21:54 回复(0)

Java

Lengxf_

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 == null || nums.length == 0) {
            return -1;
        }
        return binarySearch(nums, 0, nums.length - 1, target);
    }

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

}

编辑于 2023-12-06 11:33:26 回复(0)

Java

李克雷

import java.util.*;

public class Solution {
    /**
     * 实现无重复数字的升序数组的二分查找
     *
     * 给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，
     * 如果目标值存在返回下标（下标从 0 开始），否则返回 -1
     *
     *
     * @param nums int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public int search (int[] nums, int target) {
        if (null == nums || nums.length == 0) {
            return -1;
        }
        return getTarget(nums, 0, nums.length - 1, target);
    }

    private  int getTarget(int[] nums, int startIndex, int lastIndex, int target) {
        //如果查找范围异常，返回-1
        if (lastIndex - startIndex < 0) {
            return -1;
        }
        //获取中间节点的下标
        int mid = getMid(startIndex, lastIndex);
        if (target == nums[mid]) {
            return mid;
        }
        //目标比中间节点大，说明目标可能在中间节点右边，将查找下限设置为中间节点的下标
        if (target > nums[mid]) {
            startIndex = mid + 1;
        }
        //目标比中间节点小，说明目标可能在中间节点左边，将查找上限设置为中间节点的下标
        else  {
            lastIndex = mid - 1;
        }
        //使用新的查找范围，再次查找目标
        return getTarget(nums, startIndex, lastIndex, target);
    }

    /**
     * 获取中间下标
     *
     *
     * @param start int整型 最小下标
     * @param end int整型 最大下标
     * @return int整型 中间下标
     */
    public  int getMid(int start, int end) {
        return (start + end) >> 1;
    }

}

发表于 2023-10-11 21:55:20 回复(0)

Java

青年阿福

java解题代码，亲测通过

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, right = nums.length;
        if (target == nums[0]) {
            return 0;
        } else if (nums[right - 1] == target) {
            return  nums.length - 1;
        } else {
            while (left < right) {
                int midIndex = (left + right) / 2;
                if (nums[left] == target) {
                    return left;
                } else if (right!=nums.length && nums[right] == target) {
                    return right;
                } else {
                    if (nums[midIndex] == target) {
                        return midIndex;
                    } else if (nums[midIndex] > target) {
                        right = midIndex - 1;
                    } else {
                        left = midIndex + 1;
                    }
                }
            }
            return -1;
        }
    }

    public static void main(String[]  args) {
        Scanner scanner = new Scanner(System.in);
        if (scanner.hasNext()) {
            String inputLine = scanner.nextLine().trim();
            System.out.println(inputLine);
            if (inputLine.startsWith("[]")) {
                System.out.println(-1);
                return;
            }
            String[] numsAndTarget = inputLine.split("],");
            String[] numStrArray = numsAndTarget[0].substring(1).split(",");
            int[] nums = new int[numStrArray.length];
            for (int i = 0; i < numStrArray.length; i++) {
                nums[i] = Integer.parseInt(numStrArray[i]);
            }
            String target = numsAndTarget[1];
            int targetNum = Integer.parseInt(target);
            Solution binarySearch = new Solution();
            int index = binarySearch.search(nums, targetNum);
            System.out.println(index);
        }
    }
}

发表于 2023-08-06 02:06:20 回复(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

BlueProtocol

public class Solution {
    public int search (int[] nums, int target) {
        // write code here
        if(nums == null) return -1;
        int low = 0;
        int high = nums.length-1;
        while(low <= high) {
            int mid = (low + high)/2;
            if(target > nums[mid]) {
                low = mid+1;
            }
            else if(target < nums[mid]) {
                high = mid-1;
            }
            else return mid;
        }

        return -1;
    }
}

发表于 2023-06-29 17:07:32 回复(0)

提交观点

问题信息

二分

上传者：牛客301499号

难度：

63条回答 527收藏 6234浏览

通过挑战的用户

查看代码

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

输入

输出

说明

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题