本文共 1195 字,大约阅读时间需要 3 分钟。
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
利用二分查找法,因为是有序数组,这就简单了许多,只需要每次比较mid的值与目标值就行了,分两种情况:
第一:如果目标值存在,等于中间值则直接返回,每一次比较如果大于中间值,那么下一次在右边区间寻找,如果小于目标值,则每一次在左边区间寻找。
第二:如果目标值不存在,则插入返回插入位置的目标值。
第一步:left和right赋初始值。
第二步:明确三种情况,就是mid的值与target的大小,大于等于或小于。通过代码通过示例结合代码一步步解析。
class Solution { public int searchInsert(int[] nums, int target) { int left=0, right = nums.length-1; while(left<=right){ int mid = (left+right)/2; if(nums[mid]==target){ return mid; }else if(nums[mid]target时,搜索左边 right = mid -1; } } return left; }}
代码解析:通过示例2,目标值不存在于给出的数组来详细解析一下二分查找过程。
第一轮:target = 2; left = 0; right = 3; mid = 1; nums[mid] = 3;进入if判断条件,满足第三种情况,这时就要搜索左边区域了。
第二轮:target = 2; left = 0; right = 0; mid = 0; nums[mid] = 1;进入if判断,此时满足第二种情况,搜索右边区域。
第三轮:target = 2; left = 1; right = 0; 这时while循环条件left<=right判断为false,返回left。
这里解释一下为什么要返回left,在这个示例中,最后nums[left] = 3,插入位置是1和3之间,返回left相当于将该位置当前元素及其他元素统一后移一位,此时的该位置的值是target。另外由于while循环中是left<=right,所以每次最后一轮都会是left>right的情况才会跳出循环,每次target值插入的位置也必将是最后一轮left对应的值的左边。
转载地址:http://qogki.baihongyu.com/