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）
給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，如果找到目標(biāo)，則返回索引。如果沒(méi)有仅父，返回索引的位置，如果它是按順序插入轻要。
您可以假設(shè)數(shù)組中沒(méi)有重復(fù)項(xiàng)沾鳄。
tag
- Array 數(shù)組
- Binary Search 二進(jìn)制搜索
解法
1.自己的 循環(huán)遍歷數(shù)組
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;
}
}
時(shí)間復(fù)雜度 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);
}
}
遞歸的時(shí)間復(fù)雜度不好估箕戳，但是明顯比 單純想法 1 慢了
以下開(kāi)始搜索網(wǎng)絡(luò)了
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;
}
}
