Нахождение середины массива, не зная длины

Question

Найти середину строки или массива с неизвестной длиной. Ты можешь не пересекайте список, чтобы найти длину. Вы не можете использовать что-либо для поможет вам найти длину - как это «неизвестно». (т.е. без размера (C) или количества (C #) и т. д.)

У меня был этот вопрос как вопрос интервью. Мне просто интересно, каков ответ. Я спросил, могу ли я использовать sizeof, он ответил: «Нет, размер строки или массива неизвестен - вам просто нужно добраться до середины».

Кстати, я не уверен, что это действительно возможно решить без обхода. Я почти чувствовал, как будто он хотел видеть, насколько я уверен в своем ответе: S не уверен ...

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

Answer 1

Есть два счетчика, c1 и c2. Начните обход списка, увеличивая c1 каждый раз и c2 каждый раз. К тому времени, когда с1 дойдет до конца, с2 будет в середине.

Вы не «просмотрели список, чтобы найти длину», а затем разделили его на два, вы только что прошли один раз.

Единственный другой способ, который я могу придумать, - это продолжать снимать первый и последний элемент списка, пока у вас не останется один или несколько пунктов в середине.

Answer 2

1. Вы (или ваш интервьюер) очень расплывчаты в данных (вы упомянули "строку" и "массив");нет никаких предположений, которые могут быть сделаны, поэтому это может быть что угодно.

2. Вы упомянули, что длина строки неизвестна, но из вашей формулировки может показаться, что вы (или интервьюер)) на самом деле означало сказать непознаваемое.

   а) Если оно просто неизвестно, то вопрос в том, как его можно определить?Например, в случае строк вы можете считать конец '\0'.Затем вы можете применить некоторые алгоритмы, подобные тем, которые предложены в других ответах.

   b) Если это невозможно узнать, загадка не имеет решения.Понятие середины не имеет смысла без начала и конца.

Суть в том, что вы не можете говорить о середине без начала и конца или длины.Либо этот вопрос был намеренно без ответа, либо вы не поняли его правильно.Вы должны знать больше, чем просто начало сегмента памяти и, возможно, его тип.

Answer 3

Следующий код найдет середину массива БЕЗ обхода списка

int thearray[80];
int start = (int)&thearray;
int end = (int)(&thearray+1);
int half = ((end-start) / 4)/ 2;
std::cout <<  half << std::endl;

---

РЕДАКТИРОВАТЬ:

Этот код предполагает, что вы имеете дело с реальным массивом, а не суказатель на первый элемент, такой как:
int *pointer_to_first_element = (int *)malloc(someamount);
, не будет работать, также как и с любой другой нотацией, которая ухудшает ссылку на массив в указатель на первый элемент.В основном любые обозначения, использующие *.

Answer 4

Я думаю, что эта задача также предназначена для проверки ваших навыков в анализе проблем и сборе требований. Как уже говорили другие, для решения этой проблемы нам понадобится как минимум еще один фрагмент данных.

Мой подход заключается в том, чтобы дать понять интервьюеру, что мы можем решить проблему с одним ограничением в вызове функции: вызывающая сторона должна предоставить 2 указателя, один на начало, а другой на конец массива. Учитывая эти 2 указателя и используя базовую арифметику указателей, я достигаю этого решения; пожалуйста, дайте мне знать, что вы об этом думаете.

int *findMiddleArray( int const *first, int const *last )
{
  if( first == NULL || last == NULL || first > last )
  {
    return NULL;
  }
  if( first == last )
  {
    return (int *)first;
  }
  size_t dataSize= ( size_t )( first + 1 ) - ( size_t )first,
         addFirst= ( size_t )first,
         addLast=  ( size_t )last,
         arrayLen= ( addLast - addFirst) / dataSize + 1,
         arrayMiddle= arrayLen % 2 > 0 ?  arrayLen / 2 + 1 : arrayLen / 2;

  return ( int * )( ( arrayMiddle - 1 ) * dataSize + addFirst );
}

Answer 5

Вы бы просто использовали разницу между адресами первого и последнего элементов.