10000 update documentation · invince/Leetcode@c5296f2 · GitHub
[go: up one dir, main page]
Skip to content

Commit c5296f2

Browse files
jinshendanjinshendan
committed
update documentation
1 parent 11d81ec commit c5296f2

File tree

1 file changed

+136
-0
lines changed

1 file changed

+136
-0
lines changed

‎May-LeetCoding-Challenge/First-Bad-Version/analysis.md

Lines changed: 136 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,136 @@
1+
#### Summary
2+
A direct application of the Binary Search algorithm.
3+
4+
#### Complexity
5+
* Time complexity: O(log n)
6+
* Space complexity: O(1)
7+
8+
#### Template of Binary Search (in C++)
9+
```
10+
// Return the index if the target value could be found in the array,
11+
// otherwise, return -1;
12+
int binary_search(vector<int> arr, int target) {
13+
int left = 0, right = arr.size() - 1;
14+
while(left <= right) {
15+
int mid = (right - left) / 2 + left;
16+
if (arr[mid] == target) {
17+
return mid;
18+
}
19+
else if (arr[mid] > target){
20+
right = mid - 1;
21+
}
22+
else if (arr[mid] < target){
23+
left = mid + 1;
24+
}
25+
}
26+
return -1;
27+
}
28+
```
29+
30+
#### Other variants
31+
32+
1. Left bound. Find the first index i such that arr[i] == target, otherwise return -1.
33+
34+
* Using half-closed interval [L, R).
35+
```
36+
int left_bound_binary_Search(vector<int> arr, int target) {
37+
int left = 0, right = arr.size();
38+
while(left < right) {
39+
int mid = (right - left) / 2 + left;
40+
if (arr[mid] == target) {
41+
right = mid;
42+
}
43+
else if (arr[mid] > target){
44+
right = mid;
45+
}
46+
else if (arr[mid] < target){
47+
left = mid + 1;
48+
}
49+
}
50+
51+
if (left >= arr.size()) return -1;
52+
return (arr[left] == target ? left : -1);
53+
}
54+
```
55+
56+
* Using closed inteval [L, R]
57+
```
58+
int left_bound_binary_Search(vector<int> arr, int target) {
59+
int left = 0, right = arr.size() - 1;
60+
while(left <= right) {
61+
int mid = (right - left) / 2 + left;
62+
if (arr[mid] == target) {
63+
right = mid - 1;
64+
}
65+
else if (arr[mid] > target){
66+
right = mid - 1;
67+
}
68+
else if (arr[mid] < target){
69+
left = mid + 1;
70+
}
71+
}
72+
73+
if (left >= arr.size()) return -1;
74+
return (arr[left] == target ? left : -1);
75+
}
76+
```
77+
78+
2. Right bound. Find the last index i such that arr[i] == target, otherwise return -1.
79+
80+
* Using half-closed interval [L, R).
81+
```
82+
int right_bound_binary_Search(vector<int> arr, int target) {
83+
int left = 0, right = arr.size();
84+
while(left < right) {
85+
int mid = (right - left) / 2 + left;
86+
if (arr[mid] == target) {
87+
left = mid + 1;
88+
}
89+
else if (arr[mid] > target){
90+
right = mid - 1;
91+
}
92+
else if (arr[mid] < target){
93+
left = mid + 1;
94+
}
95+
}
96+
if (left == 0) return -1;
97+
else return (arr[left - 1] == target ? (left - 1) : -1);
98+
}
99+
```
100+
101+
* Using closed inteval [L, R]
102+
```
103+
int right_bound_binary_Search(vector<int> arr, int target) {
104+
int left = 0, right = arr.size() - 1;
105+
while(left <= right) {
106+
int mid = (right - left) / 2 + left;
107+
if (arr[mid] == target) {
108+
left = mid + 1;
109+
}
110+
else if (arr[mid] > target){
111+
right = mid - 1;
112+
}
113+
else if (arr[mid] < target){
114+
left = mid + 1;
115+
}
116+
}
117+
118+
if (right < 0) return -1;
119+
return (arr[right] == target ? right : -1);
120+
}
121+
```
122+
123+
124+
These templates are also available [here](https://github.com/jinshendan/Leetcode/tree/master/Template/Maths/Binary-Search).
125+
126+
127+
#### Remarks
128+
* Use
129+
```
130+
mid = (right - left) / 2 + left
131+
```
132+
instead of
133+
```
134+
mid = (left + right) / 2
135+
```
136+
to avoid any overflow in intermediare calculation.

0 commit comments

Comments
 (0)
0