12

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>

int main(){
    int i = 0, n = 0, first = 0, last = 0, middle = 0, targed = 0, index = 1, a = 0, b = 0;
    scanf("%d %d", &n, &targed);

    int* arr = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    printf("Initial array:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\nLinear search:\n");
    arr[n] = targed;//линейный
    while (arr[i] != targed){
        printf("%d ", arr[i]);
        i++;
    }
    if (arr[i] == targed)
        printf("%d ", targed);


    printf("\nBinary search:\n");
    last = n - 1;//бинарный
    middle = (first + last) / 2 + 1;
    printf("%d ", middle);
    while (first <= last){
        if (middle != n - 1)
            printf("%d ", arr[middle]);
        if (arr[middle] == targed){
            printf("%d", arr[middle]);
            break;
        }
        else if (arr[middle] > targed){
            last = middle;
            middle = (first + last) / 2;
        }
        else if (arr[middle] < targed){
            first = middle;
            if (middle == n - 2){
                middle = (first + last) / 2 + 1;
            }
            else
                middle = (first + last) / 2;
        }

    }


    //1 2 3 4 5 15 32
    printf("\n\nDoubling search:");
    while (arr[index] < targed)//даблинг

            index *= 2;


    first = index / 2;
    last = index;
    middle = (first + last) / 2;
    while (arr[i] < first){
        i++;
        if (arr[i] < first)
            a = arr[i];
    }
    i = 0;
    while (arr[i] < last / 2){
        i++;
        if (arr[i] < last)
            b = arr[i];
    }


    while (first <= last){
        if (arr[middle] == targed){
            //printf("El has index: %d", middle + 1);
            break;
        }
        else if (arr[middle] > targed)
            last = middle - 1;
        else if (arr[middle] < targed)
            first = middle + 1;
        middle = (first + last) / 2;
    }

    //if (first > last)
        //printf("Not found el");

    printf("%d %d", a, b);

    return 0;
}