diff options
| Commit | 5240ae0fff4cbff28e6a852606f1dc3096d8b8bf (patch) | |
|---|---|---|
| Author | 2018-10-17 21:54:55 +0300 | |
| Committer | 2018-10-17 21:54:55 +0300 | |
| Files | 2dc1f0f4d5fb72a7ae812ee8d8db19f63949a10b /homework/81281/c2html/test.c | |
| IPL-5240ae0fff4cbff28e6a852606f1dc3096d8b8bf.tar IPL-5240ae0fff4cbff28e6a852606f1dc3096d8b8bf.tar.gz IPL-5240ae0fff4cbff28e6a852606f1dc3096d8b8bf.zip | ||
| Parent | f530ae1938494a31de7c6766021fa62525f10ef9 (diff) | |
Adding first HW to repo. (#7)
* Create README.md
* Initial commit
* Initial commit
* Create README.md
* Rename homework/81281/c2html.pl to homework/81281/c2html/c2html.pl
* Rename homework/81281/test.c to homework/81281/c2html/test.c
* Update README.md
* Update README.md
* Update c2html.pl
* Update c2html.pl
* Update c2html.pl
* Update README.md
* Update c2html.pl
* Update test.c
* Create executeProgram.sh
* Update README.md
1 files changed, 87 insertions, 0 deletions
| -rw-r--r-- | homework/81281/c2html/test.c | 87 |
diff --git a/homework/81281/c2html/test.c b/homework/81281/c2html/test.c new file mode 100644 index 0000000..7176890 --- /dev/null +++ b/homework/81281/c2html/test.c @@ -0,0 +1,87 @@ +#include <stdio.h> +#include <stdlib.h> +#include <time.h> +int N = 0; +int a[750001] = {0}; +/*Problem Secrect DAA*/ +//// mauuu + +void swap(int* i, int* j) +{ + int t = *i; + *i = *j; + *j = t; +} + +int partition(int l, int r) +{ + int randIdx = l + rand() % (r - l); + + int pivot = a[randIdx]; + + swap(&a[l], &a[randIdx]); + int ind = l; + + for (int i = l + 1; i < r; ++i) + { + if (a[i] <= pivot) + { + ind++; + swap(&a[i], &a[ind]); + } + } + + swap(&a[l], &a[ind]); + return ind; +} + +void quickSort(int l, int r) +{ + if (l < r) + { + int idx = partition(l, r); + quickSort(l, idx); + quickSort(idx + 1, r); + } +} + +int binarySearch(int k) +{ + int middle, left = 0, right = N - 1; + if (k < a[left]) + return (-1); + if (k == a[left]) + return (left + 1); + if (k > a[right]) + return (-1); + + while (right - left > 1) + { + middle = (left + right) / 2; + if (k <= a[middle]) + right = middle; + else + left = middle; + } + return ((right <= N - 1 && a[right] == k) ? (right + 1) : (-1)); +} + +int main() +{ + srand(time(0)); + scanf("%d", &N); + for (int i = 0; i < N; ++i) + { + scanf("%d ", &a[i]); + } + quickSort(0, N); + + int tmp = 0; + scanf("%d", &tmp); + while (tmp != 0) + { + printf("%d\n", binarySearch(tmp)); + scanf("%d", &tmp); + } + return 0; +} |
