Difficulty: Medium
【题目】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
翻译
查找插入位置
难度系数：中等
给定一个有序数组和一个目标值，如果找到目标值则返回该索引。如果不能，返回按照顺序它应被插入位置的索引。
一些示例
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
// 二分检索 时间复杂度log2(n)
- (int)searchInsertPosition:(NSArray<NSNumber *> *)sortedArray targetValue:(NSNumber *)target {
if (sortedArray.count == 0) {
return 0;
}else {
int left = 0;
int right = (int)sortedArray.count - 1;
while(left <= right) {
int mid = (left+right)/2;
if (sortedArray[mid] == target)
return mid;
else if (sortedArray[mid] > target)
right = mid-1;
else
left = mid+1;
}
// left>right
return left;
}
}
之前学的C全就着馒头进肚子了。原谅我现阶段只会用OC来写，看起来不是很方便，最近在学Python，以后用Python写吧
