🍗二分查找合集

题1：二分查找 I

题目来源：[NC]160. 二分查找 I

题目

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

给定一个 元素有序的（升序）长度为 n 的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中出现的 target 的下标，如果目标值存在返回下标，否则返回 -1

数据范围：
进阶：时间复杂度 ，空间复杂度

时间复杂度：，其中 是数组的长度。

空间复杂度：

我的代码

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

题2：二分查找 II

题目来源：[NC]105. 二分查找 II

题目

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

给定一个 元素有序的（升序）长度为 n 的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的第一个出现的 target 的下标，如果目标值存在返回下标，否则返回 -1

数据范围：
进阶：时间复杂度 ，空间复杂度

示例1

输入：[1,2,4,4,5],4 返回值：2 说明： 从左到右，查找到第 1 个为 4 的，下标为 2 ，返回 2

时间复杂度：，其中 是数组的长度。

空间复杂度：

我的代码

public class Solution {
    public int search (int[] nums, int target) {
        int start=0;
        int end =nums.length-1;
        while(start<=end){
            if(nums[start]==target)return start;    //1. 此处相等一定下标最小
            int mid=start+(end-start)/2;
            if(nums[mid]==target){                    //2. 找到也继续向左区间找，但不丢失mid
                end=mid;                            
            }
            else if(nums[mid]<target){                
                start=mid+1;
            }else{
                end=mid-1;
            }
        }
        return -1;
    }
}