LeetCode35. 搜索插入位置

本是古典何须时尚 2023-10-09 14:19 14阅读 0赞

package leetCodeNumber;
    
    /**
     * @ClassName LeetCode35
     * @Description 搜索插入位置
     *      题目难度：简单
     *      考查知识点：数组、二分查找
     * @Author Jiangnan Cui
     * @Date 2022/6/5 19:28
     * @Version 1.0
     */
    public class LeetCode35 {
        /**
         * 题目描述：
         *     给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，
         * 返回它将会被按顺序插入的位置。
         * 请必须使用时间复杂度为 O(logn) 的算法。
         * 链接：https://leetcode.cn/problems/search-insert-position
         */
    
        /**
         * @MethodName searchInsert
         * @Description 搜索插入位置
         *      时间复杂度：O(logN）
         *      空间复杂度：O(1)
         * @param: nums
         * @param: target
         * @return: int
         * @Author Jiangnan Cui
         * @Date 2022/6/5 19:32
         */
        public static int searchInsert(int[] nums, int target) {
            //指定二分查找的左右边界left、right
            int left = 0, right = nums.length - 1;
            //二分查找范围约束
            while (left <= right){
                //计算中点，为避免整型溢出，此处不使用(left + right) / 2
                int mid = (right - left) / 2 + left;
                //比较中间值和目标值
                if(nums[mid] == target){
                    return mid;//中间值等于目标值，直接返回
                }else if(nums[mid] < target){
                    left = mid + 1;//中间值小于目标值，向右查找，查找范围为[mid+1,right]
                }else{
                    right = mid - 1;//中间值大于目标值，向左查找，查找范围为[left,mid-1]
                }
            }
            //当不满足查找范围时，左边界即为要插入新元素的位置
            return left;
        }
    
        public static void main(String[] args) {
            //测试用例
            int[] nums = {1,3,5,6};
            int target1 = 5;
            int target2 = 2;
            int target3 = 7;
    
            //测试
            System.out.println(searchInsert(nums, target1));
            System.out.println(searchInsert(nums, target2));
            System.out.println(searchInsert(nums, target3));
        }
    }