Finding the middle of an array without knowing the length

Question

Find the middle of a string or array with an unknown length. You may not cross the list to find the length. You cannot use anything to help you find the length - since it is "unknown". (i.e. no sizeof (C) or count (C #), etc.)

I had this question as a question for an interview. I'm just wondering what the answer is. I asked if I could use sizeof, he said: "No, the size of the string or array is unknown - you just need to get to the middle."

By the way, I'm not sure that it is really possible to solve without going through. I almost felt that he might have wanted to see how confident I was in his answer: S not sure ...

His English was poor - also not sure if this contributed to misunderstandings. He directly told me that I did not need to cross the list to get to the middle: S: S I assume that he meant not to cross at all .....: S

Answer 1

There are two counters, c1 and c2. Start iterating over the list, incrementing c1 each time and c2 each time. By the time c1 is completed, c2 will be in the middle.

You didn’t “move the list to find the length” and then split it into two, you just went once.

The only other way I can think of is to keep the first and last element of the list until you stay with it (s) in the middle.

Answer 2

• ( ) , ( "" "" ); , , .

• , , , ( ) .

  a) , : ? , '\0'. , , .

  b) , . .

, . , . , , , .

Answer 3

WITHOUT,

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

.

Answer 5

, ​​ . , .

My approach is to make it clear to the interviewer that we can solve the problem with one limitation in the function call: the caller must provide 2 pointers, from one to the beginning and the other to the end of the array. Given these 2 pointers and using basic pointer arithmetic, I achieve this solution; please let me know what you think about this.

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 );
}