零基础学数据结构|搜索插入位置(java) 零基础学数据结构|acm

题目 【零基础学数据结构|搜索插入位置(java)】给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:

输入: [1,3,5,6], 5 输出: 2

示例 2:

输入: [1,3,5,6], 2 输出: 1

示例 3:

输入: [1,3,5,6], 7 输出: 4

示例 4:

输入: [1,3,5,6], 0 输出: 0

算法与思路分两步：
第一步，在数组中找到目标值，并返回其索引;
第二步，不在数组中，返回它将会被按顺序插入的位置。

/**search-insert-position-两次循环法*/ public int searchInsert_1(int[] nums, int target) { int index = indexOf(nums,target); if(index!=-1) { return index; } return insert(nums,target); } /**查询索引*/ private int indexOf(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { if(nums[i]==target) { return i; } } return -1; } /**插入*/ private int insert(int[] nums, int target) { int j=0; for (j = 0; j < nums.length; j++) { if(nums[j]>target) { break; } } return j; }

仔细分析题目后，发现一步也可以。只要找到在数组中，大于等于target的元素的下标即可。

/**search-insert-position-一次循环法*/ public int searchInsert_2(int[] nums, int target) { int i; for (i = 0; i < nums.length; i++) { if(nums[i]>=target)return i; } return i; }

进一步优化，采用二分查找算法

class Solution { public int searchInsert(int[] nums, int target) { if(targetnums[nums.length-1]) { return nums.length; } int left = 0; int right = nums.length-1; int mid = right >>> 1; int leftP = -1; //先找最上位置 while(left<=right) { if(nums[left]==target) { leftP = left; break; }else if(right<=left+1) { //避免死循环 leftP = right; break; } if(nums[left]>> 1; } return leftP; } }