From 5240ae0fff4cbff28e6a852606f1dc3096d8b8bf Mon Sep 17 00:00:00 2001 From: YanaRG Date: Wed, 17 Oct 2018 21:54:55 +0300 Subject: 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 --- homework/81281/c2html/test.c | 87 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 87 insertions(+) create mode 100644 homework/81281/c2html/test.c (limited to 'homework/81281/c2html/test.c') 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 +#include +#include +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; +} -- cgit v1.3.1-26-gb76a