FilesExpand file tree

 master

/

searchForRange.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

106 lines (89 loc) · 2.36 KB

 master

/

searchForRange.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

106 lines (89 loc) · 2.36 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

98

99

100

101

102

103

104

105

106

// 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);

/*

* O(log n) solution must be something like binary search.

*

* So, we can use the binary search to find the one postion - `pos`

*

* then, we can keep using the binary search find the target in A[0..pos-1] and A[pos+1..n]

*

* The code below is self-explaination

*/

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;

}