Метка: алгоритмы

bool search(int value, int values[], int n)
{
    // смотрим кол-во элементов в массиве, если деление на %2 дает остаток 0, значит, четное кол-во
    // иначе нечетное. Если четное - делим отсортированный массив на 2, смотрим последний элемент в левой части. Сравниваем с искомым.
    // Если нечетное, то вычитаем 1 элемент, делим на 2, смотрим последний элемент в левой части +1.
    // search(needle, haystack, size), где 1 - то, что ищем в массиве; 2 - массив; 3 - размер массива

    int a = 0; //начало массива
    int b = n-1; // конец массива
    int m = b-a; // длина выбранной части массива
    int centr, levo, pravo, i;
    int aa=values[0];
    int bb=values[n-1];
    
   if (aa<=value && bb>=value) 
   {
    do
    {
        float j = m%2; //для определения четного или нечетного
        if (j==0) //если нечетное кол-во элементов в массиве
        {
            centr = (b-a)/2+a;
            if (values[centr]>value)
            {
                b=centr-1;
            }
            else if ((values[centr]<value))
            {
                a=centr+1;
            }
            else return true;
        }
        else // если четное кол-во элементов в массиве
        {
            levo = (b-a+1)/2+a-1;
            pravo = (b-a+1)/2+a;
            if (values[levo]>=value)
            {
                b=levo;
            }
            else
            {
                a=pravo;
            }
        }
        m = b-a;
    
    printf("\na=%i b=%i\n", a, b);
    for (i=a;i<=b;i++)
    {
        printf("%i\n",values[i]);
    }
    
    }
    while (m!=0);
    
// запускаем последний этап проверки, т.к. если остался 1 элемент в конце m может быть равным 0 и цикл закончится

    if (values[a]==value) return true;
    else return false;
       
   }  else return false;
}

 

bool search(int value, int values[], int n)
{
// search(needle, haystack, size), где 1 - значение из командой строки, которую ищем в стоге; 2 - массив; 3 - размер массива, номер элемента в массиве
    int i;
    if (n<=0) return false;
    else
    {
        for (i=0; i<n; i++)
        {
            if (value == values[i]) return true;
        }
    }
    return false;
}

Реализация метода пузырьковой сортировки (попарное сравнение и смена места в массиве)

void sort(int values[], int n) // sort(haystack, size); - массив + его размер
{
    if (n<1) return;
    else
    {
        int i, a, b;
        int j=1;

        do
        {
            j=0;
            for (i=1; i<n; i++)
            {
                a = values[i-1];
                b = values[i];
                
                if (values[i]<values[i-1])
                {
                    values[i] = a;
                    values[i-1] = b;
                    j=1;
                }
            }
        }
        while (j!=0);
        
        return;
    }
}