JAVA练习336- 搜索插入位置

题目概览给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。请必须使用时间复杂度为O(log n)的算法。示例 1:输入:nums [1,3,5,6], target 5输出:2示例 2:输入:nums [1,3,5,6], target 2输出:1示例 3:输入:nums [1,3,5,6], target 7输出:4提示:1 nums.length 10^4-10^4 nums[i] 10^4nums为无重复元素的升序排列数组-10^4 target 10^4来源35. 搜索插入位置 - 力扣LeetCode解题分析方法二分查找从数组中间索引开始找令该索引为 mid开始索引为 i结束索引为 j则mid ( i j ) / 2nums[ mid ] target 时返回nums[ mid ] target 时说明在左边j mid - 1nums[ mid ] target 时说明在右边i mid 1不断缩小直到 i j 即可。时间复杂度O(logn)空间复杂度O(1)class Solution { public int searchInsert(int[] nums, int target) { int n nums.length; int i 0, j n-1; while(i j) { int mid (i j) / 2; if (nums[mid] target) { return mid; } if (nums[mid] target) { i mid 1; } else { j mid - 1; } } return nums[i] target ? i 1: i; } }