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
这就是普通的二分查找,需要注意的地方代码注释中都有。其中特别注意的是：middle=（low+high）/ 2 ，可能会溢出，可以替换为middle = low + ((high - low)>>2);
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class
Solution {
public
:
int
searchInsert(
int
A[],
int
n,
int
target) {
//二分查找
int
low = 0, high = n-1;
//注意这里high是初始化为n-1
while
(low <= high)
//注意这里是<=号
{
//int middle = (low + high) / 2;
int
middle = low + ((high - low)>>2);
//可以防止low + high 溢出
if
(A[middle] < target)
low = middle + 1;
else
if
(A[middle] > target)
high = middle - 1;
else
return
middle;
}
return
low;
//注意返回值是low
}
};
|
根据程序员编程艺术第二十五章：Jon Bentley：90%无法正确实现二分查找, 如果high初始化为n, 那么while判断语句就应该是low<high, 下面的A[middle] > target分支中,就应该是high = middle
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
看到这个有没有想到STL中的equal_range函数,这个函数是调用lower_bound和upper_bound, 下面我们仿照STL的实现。相比上一题的二分查找，lower_bound当A[middle] == target时，继续向左半部分查找，它返回的是第一个不小于目标数的元素位置；upper_bound当A[middle] == target时，继续向右半部分查找，它返回的是第一个大于目标数的元素位置。 本文地址
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
class
Solution {
public
:
vector<
int
> searchRange(
int
A[],
int
n,
int
target) {
vector<
int
> res(2, -1);
int
low = 0, high = n-1;
while
(low <= high)
{
int
middle = low + ((high - low)>>2);
if
(A[middle] < target)
low = middle + 1;
else
if
(A[middle] > target)
high = middle - 1;
else
{
res[0] = lowerBound(A, low, middle - 1, target);
res[1] = upperBound(A, middle + 1, high, target) - 1;
return
res;
}
}
return
res;
}
//找到范围内[left,right]内第一个不小于target的元素
int
lowerBound(
int
A[],
int
left,
int
right,
int
target)
{
int
low = left, high = right;
while
(low <= high)
{
int
middle = low + ((high - low)>>2);
if
(A[middle] < target)
low = middle + 1;
else
high = middle - 1;
}
return
high + 1;
//注意这里返回值不是low
}
//找到范围[left,right]内第一个大于target的元素
int
upperBound(
int
A[],
int
left,
int
right,
int
target)
{
int
low = left, high = right;
while
(low <= high)
{
int
middle = low + ((high - low)>>2);
if
(A[middle] <= target)
low = middle + 1;
else
high = middle - 1;
}
return
low;
}
};
|
