Repository navigation
Expand file tree
/
Copy pathsearchForRange.cpp
More file actions
97 lines (80 loc) · 2.09 KB
/
Copy pathsearchForRange.cpp
File metadata and controls
97 lines (80 loc) · 2.09 KB
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// Source : https://oj.leetcode.com/problems/search-for-a-range/
// Author : Hao Chen
// Date : 2014-06-26
/**********************************************************************************
*
* 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].
*
*
**********************************************************************************/
#include <iostream>
#include <vector>
using namespace std;
int binary_search(int A[], int low, int high, int key);
vector<int> searchRange(int A[], int n, int target) {
int pos = binary_search(A, 0, n-1, target);
vector<int> v;
int low = -1, high = -1;
if (pos >=0){
low = high = pos;
int l = low;
do {
low = l;
l = binary_search(A, 0, low - 1, target);
}while (l>=0);
int h = high;
do {
high = h;
h = binary_search(A, high + 1, n-1, target);
}while (h>=0);
}
v.push_back(low);
v.push_back(high);
return v;
}
int binary_search(int A[], int low, int high, int key){
while (low<=high) {
int mid = low + (high-low)/2;
if (A[mid] == key) {
return mid;
}
if (key > A[mid]) {
low = mid + 1;
}
if (key < A[mid]) {
high = mid - 1;
}
}
return -1;
}
void printVector( vector<int>& pt)
{
cout << "{ ";
for(int j=0; j<pt.size(); j++){
cout << pt[j] << " ";
}
cout << "} " << endl;
}
int main()
{
const int cnt=6;
int a[cnt] ={5, 7, 7, 8, 8, 10};
vector<int> v;
v = searchRange(a, cnt, 8);
printVector(v);
int b[cnt] ={5, 5, 5, 8, 8, 10};
v = searchRange(b, cnt, 5);
printVector(v);
int c[cnt] ={5, 5, 5, 5, 5, 5};
v = searchRange(c, cnt, 5);
printVector(v);
return 0;
}