-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.c
163 lines (137 loc) · 3.99 KB
/
main.c
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <stdio.h>
#include <stdlib.h>
// find the element in the array which is equal to the target
int binarySearch(int *arr, int target, int size) {
int low = 0;
int high = size - 1;
int mid;
while(low <= high) {
mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if(arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
// find the first element in the array which is greater than(>) the target
int binarySearchGreater(int *arr, int target, int size) {
int low = 0;
int high = size;
int ans = -1;
while(low <= high) {
int mid = (low + high) / 2;
if (arr[mid] <= target) {
low = mid + 1;
} else {
ans = mid;
high = mid - 1;
}
}
return ans;
}
// find the first element in the array which is greater or equal(>=) than the target
int binarySearchGreaterOrEuqal(int *arr, int target, int size) {
int low = 0;
int high = size;
int ans = -1;
while(low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
ans = mid;
high = mid - 1;
}
}
return ans;
}
// find the last element in the array which is smaller(<) than the target
int binarySearchSmaller(int *arr, int target, int size) {
int low = 0;
int high = size - 1;
int ans = -1;
while(low <= high) {
int mid = (low + high) / 2;
if (arr[mid] < target) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}
// find the last element in the array which is smaller or equal(<=) than the target
int binarySearchSmallerOrEqual(int *arr, int target, int size) {
int low = 0;
int high = size - 1;
int ans = -1;
while(low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}
int testGreaterThan() {
printf("Test strictly greater search.\n");
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 16};
int target[] = {0, 2, 7, 14, 15, 20};
for (int j = 0; j < sizeof(target)/sizeof(int); j++) {
int t = target[j];
int i = binarySearchGreater(arr, t, sizeof(arr)/sizeof(int));
printf("find: %d %d\n", t, i >= 0 ? arr[i] : -1);
}
return 0;
}
int testGreaterEqual() {
printf("Test greater or equal search\n");
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 16};
int target[] = {0, 2, 7, 14, 15, 20};
for (int j = 0; j < sizeof(target)/sizeof(int); j++) {
int t = target[j];
int i = binarySearchGreaterOrEuqal(arr, t, sizeof(arr)/sizeof(int));
printf("find: %d %d\n", t, i >= 0 ? arr[i] : -1);
}
return 0;
}
int testSmallerThan() {
printf("Test smaller search\n");
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 16};
int target[] = {0, 2, 7, 14, 15, 20};
for (int j = 0; j < sizeof(target)/sizeof(int); j++) {
int t = target[j];
int i = binarySearchSmaller(arr, t, sizeof(arr)/sizeof(int));
printf("find: %d %d\n", t, i >= 0 ? arr[i] : -1);
}
return 0;
}
int testSmallerOrEqual() {
printf("Test smaller or equal search\n");
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 16};
int target[] = {0, 2, 7, 14, 15, 20};
for (int j = 0; j < sizeof(target)/sizeof(int); j++) {
int t = target[j];
int i = binarySearchSmallerOrEqual(arr, t, sizeof(arr)/sizeof(int));
printf("find: %d %d\n", t, i >= 0 ? arr[i] : -1);
}
return 0;
}
int main() {
testGreaterThan();
testGreaterEqual();
testSmallerThan();
testSmallerOrEqual();
}