本文主要是介绍100. Search Insert Position,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6]
, 5 → 2
[1,3,5,6]
, 2 → 1
[1,3,5,6]
, 7 → 4
[1,3,5,6]
, 0 → 0
Subscribe to see which companies asked this question
分析:给定一个排好序的非递减数组和关键字target,如果target在数组中存在,则返回target在数组中第一次出现的下标。如果target不在数组中存在 ,则返回target应该插入的下标。前半部分采用二分查找的方式找元素下标,如果查找到则返回的下标为该元素在数组中首次出现的下标。用二分查找得到一个下标low,由于初始化和循环的控制条件,这个low在nums的合法下标内,所以可以直接判断如果nums[low]>=target, 则返回low即可。否则返回low+1.
/*** 给定一个排好序的非递减数组和关键字target,如果target在数组中存在,则返回target在数组中第一次出现的下标。* 如果target不在数组中存在 ,则返回target应该插入的下标。* 前半部分采用二分查找的方式找元素下标,如果查找到则返回的下标为该元素在数组中首次出现的下标。* 用二分查找得到一个下标low,由于初始化和循环的控制条件,这个low在nums的合法下标内,所以可以直接判断如果nums[low]>=target,* 则返回low即可。否则返回low+1.* */public int searchInsert(int[] nums, int target) {int high = nums.length - 1;int low = 0;int mid = 0;while (low < high) {// 注意1对应注意2mid = low + (high - low) / 2; // 这样先减后加是为了防止溢出if (nums[mid] < target) {low = mid + 1;} else {high = mid; // 注意2}}// low出循环的时候肯定是在[0,high],都是数组的正常合法的下标。/* 出了while循环的low和high都已经被改变了,不再是初始化时的low和high */if (nums[low] >= target) {//如果nums[low]比target大或者二者相等,则low即为target的插入位置return low;} else {return low + 1;}}
这篇关于100. Search Insert Position的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!