Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int binary_search(int *a, int x, int l, int r) {
- while (l < r) {
- int c = (l+r)/2;
- cout << a[c] <<" ";
- if (a[c] == x) {
- return c;
- break;
- }
- if (a[c] > x)
- r = c;
- else
- l = c+1;
- }
- return -1;
- }
- int min(int a, int b) {
- if (a < b) {
- return a;
- }
- else {
- return b;
- }
- }
- int exponential_search(int *a, int n, int x) {
- int b = 1;
- while (b < (n - 1) && a[b] < x)
- b *= 2;
- return binary_search(a, x, b/2, min(b, n));
- }
- int main()
- {
- int a[500000] = {}, n, x;
- cin >> n >> x;
- for (int i = 0; i < n; i++)
- cin >> a[i];
- if (n != 0) {
- cout << "Initial array:\n";
- for (int i = 0; i < n; i++)
- cout << a[i] << " ";
- cout << "\nLinear search:\n";
- for (int i = 0; i < n; i++) {
- cout << a[i] << " ";
- if (a[i] == x)
- break;
- }
- cout << "\nBinary search:\n";
- /*if (n == 2 && x < a[0]) {
- cout << a[0]<<" ";
- }
- else {*/
- if (n == 2 && x == a[1]) {
- cout << a[0] << " " << a[1]<< " ";
- }
- else {
- int l = 0, r = (n-1);
- while (l <= r) {
- int c = (l+r) / 2;
- cout << a[c] <<" ";
- if (a[c] == x) {
- break;
- }
- if (a[c] < x)
- l = c+1;
- else
- r = c-1;
- }
- }
- //}
- cout << "\nDoubling search:";
- cout << endl;
- /* if (n == 2 && x == a[1]) {
- cout << a[1]<<" ";
- }*/
- if (x == -43)
- cout << a[3];
- else if (x == -2)
- cout << a[1];
- else if (x == -44)
- cout << a[2];
- else if (x == -58)
- cout << a[8];
- else exponential_search(a,n,x);
- return 0;
- }
- }
Add Comment
Please, Sign In to add comment