LeetCode-35-Search Insert Position

Search Insert Position

 

来自 <https://leetcode.com/problems/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

 题目解读

给定一个有序数组和一个特定的target值，如果数组中存在target，返回其在数组中的index，如果没找到，返回其插入点的位置，使该数组称为一个有序数组。

数组中的所有数都不是重复的。

例子

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

解析：

解法一：最简单的方法就是从前向后遍历，找到与target相等或者比target大但相差最小的元素的index,将index返回。

解法二：利用二分查找，找到插入点的位置。

 

 

解法一Java代码：

public class Solution {
    public int searchInsert(int[] nums, int target) {
         for(int i=0; i<nums.length; i++) {
        	if(target == nums[i] || target < nums[i])
        		return i;
        	 else {
        		if(i<nums.length-1) {
        			continue;
        		} else {
        			return nums.length;
        		}
        	}
        }
        return nums.length;
    }
}

解法一性能

 

解法二代码

public class Solution {
	/**
	 * 二分查找
	 * @param nums
	 * @param target
	 * @return
	 */
	public int searchInsert(int[] nums, int target) {
		if(nums == null)
			return 0;
		int low = 0;
		int high = nums.length-1;
		int mid = 0;;
		
		while(low < high) {
			mid = (low + high) / 2;
			if(nums[mid] == target)
				return mid;
			else if(nums[mid] > target)
				high = mid-1;
			else
				low = mid+1;
		}
		
		if(nums[low] >= target)
			return low;
		else 
			return low+1;
	}
}

 

解法二性能