-
Notifications
You must be signed in to change notification settings - Fork 0
/
11_5.cpp
99 lines (90 loc) · 2.38 KB
/
11_5.cpp
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
//
// 11_4.cpp
//
//
// Created by Pengyan Qin on 7/15/15.
//
//
#include <iostream>
#include <string>
using namespace std;
// if A[mid] is empty, move mid to left
int find_string(string A[], int left, int right, string str){
if(left > right)
return -1;
int mid = left + (right - left)/2;
int tmp = mid;
while(A[mid] == "" && mid >= left) // if A[mid] is empty, move left until non-empty or tmp < left
mid--;
if(mid < left) // search right half
return find_string(A, tmp + 1, right, str);
else{ // find non empty string in A[mid]
if(A[mid] == str)
return mid;
if(str < A[mid])
return find_string(A, left, mid - 1, str);
else
return find_string(A, mid + 1, right, str);
}
}
// if A[mid] is empty, move mid to cloest non-empty string
int find_string1(string A[], int left, int right, string str){
if(left > right)
return -1;
int mid = (left + right) >> 1;
int i = 0;
while(A[mid] == ""){
if(mid - i >= left || mid + i <= right){
if(mid - i >= left && A[mid - i] != ""){
mid = mid - i;
break;
}
else if(mid + i <= right && A[mid + i] != ""){
mid = mid + i;
break;
}
++i;
}
else
return -1;
}
if(str == A[mid])
return mid;
if(str < A[mid])
return find_string1(A, left, mid - 1, str);
else
return find_string1(A, mid + 1, right, str);
}
int find_string2(string A[], int left, int right, string str){
if(left > right)
return -1;
int mid = (left + right) >> 1;
int l = mid - 1;
int r = mid + 1;
while(A[mid] == ""){
if(l < left && r > right)
return -1;
else if(l >= left && A[l] != ""){
mid = l;
break;
}
else if(r <= right && A[r] != ""){
mid = r;
break;
}
--l;
++r;
}
if(str == A[mid])
return mid;
if(str < A[mid])
return find_string1(A, left, mid - 1, str);
else
return find_string1(A, mid + 1, right, str);
}
int main(){
string A[] = {"", "dad", "", "", "", "", "", "", "", "", "", "", ""};
int n = 13;
string str = "dad";
cout << find_string1(A, 0, n-1, str) << endl;
}