Поиск числа.

[IgnisFatuus]

И снова доброго времени суток.

На досуге придумывал прогу которая искала бы число в рандомном массиве.

Наваял вот это -

Код: (C)

#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N (10)
//#define Nmin (N-10)

int main()
{

        int massiv[N+1]; // Массив
        int i, j; // Счетчики
        int min; //Наименьший элемент массива
        int temp; //Временное хранилище
        int x; //Искомая величина
        int n=0; // Счетсик перестановок
        int L = 0;
        int R = N;
        int m;
        int flag = 0;
        int switching;



        // Заполнение массива
        srand((unsigned)time (NULL));
        for (i=0; i<N; i++)
        massiv[i] = rand()%20 +1;


        // Вывод массива на экран
        printf ("Unsorted array is: \n");
        for (i=0; i<N; i++)
        {
                printf("massiv [%d]= %d \t", i, massiv[i]);
        }



//Сортировка методом прямого выбора

        for (i = 0; i<N; i++)
                {      
                         n++;
                         min=i;
                         for (j = i+1; j< N; j++)
                        {
                                if (massiv[j]<massiv[min])min=j;
                        }
                        temp = massiv[min];
                        massiv[min] = massiv[i];
                        massiv[i]=temp;
                       
                }


// Распечатка отсортированного массива


        printf ("Sorted array is: \n");
        for (i=0; i<N; i++)
        {
                printf("massiv [%d]= %d \t", i, massiv[i]);
        }

                printf(" We did %d replaces\n" , n);

// запрос на ввод числа
       
        printf ("What number do you want to find?(0-20)\n");
        scanf ("%d", &x);

//Уточнение
        printf ("You wanna find all of them or only first? \n Enter '1' for all of them \n Or enter '2' to find first one \n");
        scanf ("%d", &switching);

//Поиск

        // Если найти 1
        if (switching==2)
        {      
                while ( L < R )
                {
                        m = (L + R) / 2;
                        if ( massiv[m] == x )
                        {
                                flag = 1;
                                break;
                        }
                        if ( x < massiv[m] ) R = m;
                        else L = m + 1;
                }
                        if ( flag )
                        printf ( "You number is massiv [%d]\n", m );
                        else printf( "There is no such element\n" );
        }

        // Если найти все
        else if (switching==1)
        {
               
                for(i=0; i<N ; i++)
                {
               
                        if(massiv[i]==x)
                        {
                                printf("It is [%d] \n", i);
                                flag = 1;
                        }
                        else (flag == 0);
                }
                if (flag==0)printf("There is no such element \n");
                               
        }

}

Функций мы пока еще "не знаем".

Как-то получилось развернуто. Что поменять?

И еще если я ищу все введенные числа - можно как-то по правильнее переписать последний кусочек?

Код: (C)

// Если найти все
        else if (switching==1)
        {
               
                for(i=0; i<N ; i++)
                {
               
                        if(massiv[i]==x)
                        {
                                printf("It is [%d] \n", i);
                                flag = 1;
                        }
                        else (flag == 0);
                }
                if (flag==0)printf("There is no such element \n");

А то я чувствую как-будто на бэйсике пишу...

Мне говорили, что можно этот поиск реализовать таким образом - оставить "Про запас 1 элемент массива "

Код: (C)

int massiv[N+1];

И вставить туда искомое число.
И в условии последовательного поиска написать условие

Код: (C)

 for(i=0; i<N &&massiv[i]!= x ; i++);

Но как я понял это работает только если надо найти только 1 элемент.

В сортировке стоит счетчик  - это я собираюсь запилить сортировку методом пузырька и показать где выполняется больше действий.

Быть может если можно реализовать код более оптимально - подскажете как?

[Dimka]

Мне показалось, что сортировка применена только потому, что используется поиск делением пополам.

Следовательно, порядок действий какой-то не такой.

Во-первых, если сортировка нужна только для поиска, то они должны образовывать единый блок - идти подряд, а не перемежаться с запросом к пользователю.

Во-вторых, такой поиск не должен "портить" массив. Следовательно, нужно сначала скопировать массив во временный, а затем отсортировать и искать элементы во временном массиве.

В-третьих, если идёт поиск самого элемента, то сортировка и поиск делением пополам годятся. Если же идёт поиск индекса элемента в исходном массиве, то остаётся только перебор: тогда сортировка и поиск делением пополам выкидываются.

В-четвёртых, поиск первого вхождения и поиск всех вхождений - это не разные задачи; вторая задача является расширением первой. Общими для них является подзадача: найти первое вхождение, начиная с такого-то индекса. Тогда поиск первого вхождение - это запуск подзадачи с начала массива. Поиск всех вхождений - это циклический запуск подзадачи, начиная с элемента, следующего за найденным (или с начала) до тех пор, пока очередной запуск не даст отсутствие искомого.

В-пятых, предыдущее решается перебором для неотсортированного массива. Если же массив отсортирован, совершенно очевидно, что несколько вхождений одного и того же будут идти подряд. И этим фактом можно воспользоваться. Например, поиск делением пополам совсем не обязательно попадёт на первое вхождение элемента. Следовательно, нужно от найденного элемента посмотреть и влево и вправо до тех пор, пока там такие же элементы, и определить левый и правый индексы всей группы одинаковых элементов.

P.S. В общем, комплекс задач не очень чётко поставлен. А правильная постановка задачи - половина решения.

[IgnisFatuus]

Пока гулял тоже понял, что сортировка нужна только для двоичного поиска.
Значит можно в принципе составить такой алгоритм :

1)Заполнение массива рандомными числами.

2) Запрос - нужно подтвердить наличие Числа в массиве(а) или указать позицию искомых чисел в массиве(б).

3) Если  (а)
{
     формируем новый массив
     Копируем исходный в новый
     Сортируем массив
     Ищем методом половинного деления.
}

4) Если (б)
{
    Поиск сравнением с каждым элементом массива.
}

5) Profit




Так?

[Dimka]

Вообще, если усложнить структуру данных, можно сделать и двоичный поиск индекса. Для этого нужно делать временный массив не чисел, а структур из числа - элемента исходного массива и числа - индекса в исходном массиве. Либо же, раз в массиве числа, двумерный массив размером Nx2. Сортировать нужно будет связки элемент-индекс, сама сортировка - по элементам. Тогда поиск делением пополам даст не только элемент, но и индекс элемента в исходном массиве.

Ещё более продвинутый вариант: структура из указателя на исходный элемент и индекса. А если использовать неочевидную арифметику указателей, то достаточно будет и одного лишь указателя - по нему всегда можно найти смещение в исходном массиве и вычислить индекс.

Наконец, можно просто завести дополнительный массив индексов, при сортировке обращаясь к элементам исходного массива.

[IgnisFatuus]

Я прошу прощения, а можно маленькие примеры? Не решение конечно, но примеры.

[Dimka]

IgnisFatuus, дык как в такой скромной задаче решение отделить от примера?

Код: (C)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10
#define M 20

int main()
{

  int a[N], t[N];
  int i, j;
  int s;
  int m, x;
  int l, c, r;

  srand((unsigned int)time(NULL));
  for(i = 0; i < N; i += 1)
  {
    a[i] = rand() % M + 1;
    t[i] = i;
  }
  for(i = 0; i < N - 1; i += 1)
  {
    m = i;
    for(j = i + 1; j < N; j += 1)
    {
      if(a[t[m]] > a[t[j]])
      {
        m = j;
      }
    }
    if(m != i)
    {
      x = t[i];
      t[i] = t[m];
      t[m] = x;
    }
  }

  printf("Array is [");
  for(i = 0; i < N; i += 1)
  {
    printf("%i", a[i]);
    if(i < N - 1)
    {
      printf(", ");
    }
  }
  printf("].\n");
  printf("What element do you want to search? ");
  scanf("%d", &s);

  l = 0;
  r = N - 1;
  while(l < r)
  {
    c = (l + r) / 2;
    if(a[t[c]] <= s)
    {
      if(l < c)
      {
        l = c;
      }
      else
      {
        r = c;
      }
    }
    if(a[t[c]] >= s)
    {
      r = c;
    }
  }
  if(a[t[c]] != s)
  {
    printf("Element is not found.\n");
  }
  else
  {
    while(a[t[l]] == s && l >= 0)
    {
      l -= 1;
    }
    l += 1;
    while(a[t[r]] == s && r < N)
    {
      r += 1;
    }
    r -= 1;
    for(i = l; i <= r; i += 1)
    {
      printf("Element %i is found in position %i.\n", a[t[i]], t[i]);
    }
  }

  return 0;

}

Здесь использован массив индексов и косвенные обращения к основному массиву. Обрати внимание, что массив индексов идёт как неотъемлемое дополнение к основному массиву, поэтому сортировка массива индексов находится в одном блоке с заполнением основного массива. Поиск же - отдельная операция, осуществляемая по обоим массивам. Поиск всегда методом деления пополам.

[IgnisFatuus]

Что-то я немного запутался... Понедельник день тяжелый... Путаюсь что для чего... Не могли бы Вы комментарии оставить?

Добавлено через 13 минут и 4 секунды:

Код: (C)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10
#define M 20

int main()
{

  int a[N], t[N];
  int i, j;
  int s;
  int m, x;
  int l, c, r;

  srand((unsigned int)time(NULL)); // Заполняем массивы, так?  Причем массив  t - массив указателей индекса, так?
  for(i = 0; i < N; i += 1)
  {
    a[i] = rand() % M + 1;
    t[i] = i;
  }
  for(i = 0; i < N - 1; i += 1)
  {
    m = i;
    for(j = i + 1; j < N; j += 1) // сортировка от минимальному к максимальном, так?
    {
      if(a[t[m]] > a[t[j]])
      {
        m = j;
      }
    }
    if(m != i) // Не ясно с этим обменом и что за условие...
    {
      x = t[i];
      t[i] = t[m];
      t[m] = x;
    }
  }

  printf("Array is [");   // Отсортированный массив?
  for(i = 0; i < N; i += 1)
  {
    printf("%i", a[i]);
    if(i < N - 1)
    {
      printf(", ");
    }
  }
  printf("].\n");
  printf("What element do you want to search? ");
  scanf("%d", &s);

  l = 0;
  r = N - 1;
  while(l < r)    // это двоичный поиск, понятно
  {
    c = (l + r) / 2;
    if(a[t[c]] <= s)
    {
      if(l < c)
      {
        l = c;
      }
      else
      {
        r = c;
      }
    }
    if(a[t[c]] >= s)
    {
      r = c;
    }
  }
  if(a[t[c]] != s)
  {
    printf("Element is not found.\n");
  }
  else
  {
    while(a[t[l]] == s) // Вот это не совсем понятно
    {
      l -= 1;
    }
    while(a[t[r]] == s) // И вот это
    {
      r += 1;
    }
    l += 1;
    r -= 1;
    for(i = l; i <= r; i += 1)
    {
      printf("Element %i is found in position %i.\n", a[t[i]], t[i]);
    }
  }

  return 0;

}

[Dimka]

Заполняем массивы, так?  Причем массив  t - массив указателей индекса, так?

Да. Только не указателей (слово в C имеет особый смысл), а самих индексов. И не в этой строчке, а ниже.

сортировка от минимальному к максимальном, так?

Да. Только это определяет не for, а if.

Не ясно с этим обменом и что за условие...

Если m (индекс минимума) не отличается от i (того индекса, который был присвоен m до начала поиска минимума - см. выше for j), то очевидно, что обмен с самим собой не нужен. Впрочем, вне зависимости от причины равенства m и i обмен с самим собой не нужен.

Отсортированный массив?

a - нет, как и задумано; t - да, как и задумано, но t отсортирован не по значениям внутри t, а так, что значения t есть индексы для a. Тут выводится a, так что не отсортирован.

Вот это не совсем понятно

Я же писал выше, что двоичный поиск найдёт какой-то элемент, но не факт, что он будет первым вхождением. В отсортированном массиве соседние элементы одинаковы - вот и ищем границы интервала одинаковых элементов.

P.S. Надо было со структур пар начинать. Косвенная индексация для неподготовленого разума - тяжеловато. Впрочем, как и указатели.

[Dimka]

В код выше добавлена существенная поправка: там, где определяется интервал одинаковых элементов, добавлены условия проверки границ массива. Без этого работает неправильно в тех случаях, когда интервал находится на левом или правом краю массива.

[IgnisFatuus]

А если бы я хотел найти лишь одно число? Как сказал препод "Мне нужен билет до Жмеринки. Не все билеты, а только 1."

Надо ведь после первого найденого поставить break? Или можно как-то обойтись без него?

[Dimka]

IgnisFatuus, я думаю, если есть доступ ко всем, то взять первое подвернувшееся - не проблема. Хоть через break, хоть по условию пропуском циклов, расширяющих интервал - в начале после завершения поиска l == r, что указывает на единственное число.