剑指offer68：查找插入位置

题目：
给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
输入: nums = [1,3,5,6], target = 5
输出: 2
输入: nums = [1,3,5,6], target = 2
输出: 1
分析：
当数组中包含目标值时，返回它再数组中的位置，由于数组中没有相同的数字，因此它前一个数字一定小于目标值，于是可以把目标值t是否在数组中出现两种情况统一起来，也就是查找满足两个条件的位置，一是该位置上的数字大于或等于t，二是该位置的前一个数字小于t。
按顺序查找数组能够找到符合条件的位置，但需要O（n）的时间复杂度，因为数组是排序的，而且是关于排序数组的查找 *** 作，因此采用二分查找法比较合适。
有两种特殊情况需要注意下，第一种情况是当mid等于0的时候如果nums[mid]依然大于目标值t，，则意味着数组中所有数字都比目标值大，应该返回0。第二种情况是当数组中不存在大于或等于目标值t的数字时，那么t应该添加到数组所有值的后面，也就是返回数组的长度。
二分查找法时间复杂度为O（logn）。
代码：

public class SearchInsert {
    public int searchInsert(int[] nums,int target){
        int left = 0;
        int right = nums.length-1;
        while (left<=right){
            int mid = (left+right)/2;
            if (nums[mid] >= target){
//                当mid等于0时，如果nums[mid]依然大于target，则说明数组中所有数组都比target大，返回0
                if (mid == 0 ||nums[mid-1]  
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5634750.html