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
翻譯
查找插入位置
難度系數(shù)：中等
給定一個(gè)有序數(shù)組和一個(gè)目標(biāo)值脖捻，如果找到目標(biāo)值則返回該索引阔逼。如果不能，返回按照順序它應(yīng)被插入位置的索引地沮。
一些示例
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
// 二分檢索 時(shí)間復(fù)雜度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;
}
}
之前學(xué)的C全就著饅頭進(jìn)肚子了嗜浮。原諒我現(xiàn)階段只會用OC來寫，看起來不是很方便诉濒，最近在學(xué)Python周伦，以后用Python寫吧
