As a programmer, most of us have at least coded the binary search algorithm: the algorithm to find a value in a sorted array. The algorithm itself is clear and easy to understand:
1
2
3
4
5
6
7
8
9
10
11
| int BinSearch::bSearch(int* arr,int n, int value){
int left = 0;
int right = n;
while (left <= right){
int mid = (int)(left+right)/2;
if (arr[mid] == value) return mid;
else if (arr[mid] < value) left = mid + 1;
else right = mid - 1;
}
return -1;
} |
However, the binary search algorithm’s capability is far beyond that. Given an array of number (real/int), we can find the element in that array which is closest to the given value. The idea is that we find a range [left,right] in array that is small enough and “close enough” to value .i.e a[left] < value < a[right], value < a[left] < a[right] or a[left] < a[right] < value:
1
2
3
4
5
6
7
8
9
10
11
12
| int BinSearch::bNearSearch(int* arr, int n, int value){
int left = 0;
int right = n;
while (right - left > 1){
int mid = (int)(left+right)/2;
if (arr[mid] == value) return mid;
else if (arr[mid] < value) left = mid;
else right = mid;
}
if (abs(value - arr[right]) < abs(value - arr[left])) return right;
else return left;
} |
That’s it !
Problem: Given a string s[0..n] and an index pos, output the rotated string s[pos,pos+1,...n,0,1,..pos].
For example: Input “ABCDEFGH” and pos = 3. Output : “DEFGHABC”.
I noticed that when I “shifted” the smaller potion of string to its correct position, the sub-problem to make larger portion in correct order is in fact the main problem on substring.
For example:
ABCDEFGH -> FGHDEABC
We see here ABC is in correct position and order. The problem now is make “FGHDE” become “DEFGH”. And …
FGHDE is in fact the rotation of DEFGH at the same position 3 !!!
In short, here is the code I wrote:
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
| void RotateString::rotate(int left, int right, int pos){
if (pos == left) return;
shift(left,right,pos);
//cout << str << " left: " << left << " right: " << right << " pos:" << pos << endl ;
int length1 = pos - left;
int length2 = right - pos + 1;
if (length1 < length2){ // 2 * pos < left + right + 1
rotate(left,left + length2 - 1, pos); // right = left + legth2 - 1 = left + right - pos >= pos
}else
rotate(left + length2, right, pos); // right > pos
//in two case right always larger than pos and left increases toward pos -> the algo stops when left reaches pos
}
void RotateString::rotate(string str,int pos){
cout << "str:"<< str << "\t length:" << str.length() <<"\t pos:" << pos << endl;
RotateString::str = str;
if (pos < str.length()){
rotate(0,str.length()-1,pos);
}
cout << "rotated string:"<<RotateString::str << endl;
}
void RotateString::shift(int left, int right,int pos){
if (2*pos > left + right){
for (int i = pos; i <= right; i++){
char temp = str[i];
str[i] = str[i- pos + left];
str[i-pos + left] = temp;
}
}
else{
//notice pos is the start of "right string" not end of "left string"
for (int i = pos-1; i >= left;i--){
char temp = str[i];
str[i] = str[right - pos + i + 1];
str[right - pos + i + 1] = temp;
}
}
} |
Another solution is to relate it to the string reversion (“My name is Nam” -> “Nam is name my”). This problem is the special case of string reversion when there are only two words in string and the delimiter is defined as a separated position (pos). In short,
1
2
3
| rorateString(string,0,n,pos) = reverse(string,0,pos-1)
&reverse(string,pos,n)
&reverse(string,0,n); |
Although both solution is O(n) in runtime, the first solution is more efficient than the second. In the first algorithm, each character is “touched” one time only before being moved to the correct position. In the second algorithm, each character is reversed two times, however.
Given an array a1, a2, a3, … an, b1, b2, b3… bn, convert it to an array a1,b2,a 2,b2,a3,b3….an,bn in O(1) space and O(n) time.
The current algorithm I came up with is O(1) space but O(n^2) running time.
I think it should have some property to make a transformation chain from the original array to the converted one like ai1->bi2->ai3-> bi4 -> …. -> ai1.