• 35. Search Insert Position
  • 题目
  • 翻译（by google）
  • tag
  • 解法
    • 1.自己的 循环遍历数组
    • 2.自己的 偏递归遍历
    • 3.别人的 二分查找(http://blog.csdn.net/linhuanmars/article/details/20278967)

35. 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.

翻译（by google）

给定一个排序数组和一个目标值，如果找到目标，则返回索引。如果没有，返回索引的位置，如果它是按顺序插入。

您可以假设数组中没有重复项。

tag

• Array 数组
• Binary Search 二进制搜索

解法

1.自己的 循环遍历数组

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        int i=0;
        for(i=0;i<nums.Length;i++) {
            if(nums[i] == target) return i;
            if(nums[i] > target) break;
        }
        return i;
    }
}

时间复杂度 O(n)

2.自己的 偏递归遍历

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        this.target = target;
        this.nums = nums;
        return Search(0);
    }
    public int target;
    public int[] nums;
    public int Search(int i) {
        if(i > nums.Length-1 ) return i;
        if(nums[i] >= target) return i;
        return Search(i + 1);
    }
}

递归的时间复杂度不好估，但是明显比 单纯想法 1 慢了

以下开始搜索网络了

3.别人的 二分查找(http://blog.csdn.net/linhuanmars/article/details/20278967)

public class Solution {
    public int SearchInsert(int[] nums, int target) {  
    if(nums == null || nums.Length == 0)  
    {  
        return 0;  
    }  
    int l = 0;  
    int r = nums.Length-1;  
    while(l<=r)  
    {  
        int mid = (l+r)/2;  
        if(nums[mid]==target)  
            return mid;  
        if(nums[mid]<target)  
            l = mid+1;  
        else  
            r = mid-1;  
    }  
    return l;  
}
}