Provide a recursive function that takes a pointer to the middle of an infinite doubly linked list along with an integer key and searches the list for the given key. The list grows infinitely in both directions. Your algorithm should be able to find the key if it is present in the list, otherwise it should continue the search infinitely. This is The question i'm provided with and i can't understand how To recursivly search on both sides. either i'll have to write 2 functions i.e one for searching left other for right side. but can it e searched in one function? this is my code:

 void searchmiddle(Node<T>* middle, int key,int index) {
       
        if (middle == NULL) {
            return  ;
        }
        if (head == NULL) {
            return  ;
        }
       /* if (middle->next == head) {
            return false ;
        }*/
        if (middle->data == key) {
            cout << "key found at  index "<<index << endl;
            key = 0;
            return ;
        }
        searchmiddle(middle->prev, key, index - 1);

         searchmiddle(middle->next, key, index   1);
         


    }

code works for key next to middle pointer..

CodePudding user response：

You should not use recursion, because the requirement is that the search should continue infinitely for as long as there is no match. The call stack is limited, and recursion consumes it, meaning the recursion cannot go on indefinitely.

By consequence, the search should happen through iteration and not recursion.

You should use two pointers, one that will move along the prev pointers to the left, and the other that will move along the next pointers to the right. As apparently it is needed to report the index where the match was found, you should accompany those two pointers with an index.

There should not be a reference to a head pointer (where is it defined?), as an infinite list has no head. The challenge description suggests that the list extends continually in both directions, so there will be no end node like a head or a tail.

The code could be something like this:

void searchmiddle(Node<T>* middle, int key, int index) {
    Node<T>* left = middle;
    int leftIndex = index;
    Node<T>* right = middle->next;
    int rightIndex = index   1;

    while (1) { // Search continues as long there is no match
        if (left->data == key) {
            cout << "key found at  index " << leftIndex << endl;
            return;
        }
        left = left->prev;
        leftIndex--;
        
        if (right->data == key) {
            cout << "key found at  index " << rightIndex << endl;
            return;
        }
        right = right->prev;
        rightIndex  ;
    }
}

This is quite a theoretical challenge, as the only way to have a really infinite linked list, is to make it circular. It also means that there is a possibility that the key will never be found giving you a function that never finishes.

CodePudding user response：

You could relay the call to a function that instead takes two Node<T>*, left and right. You then check if either one is the correct node and return if anyone is, otherwise you call the same function again recursively while stepping both left and `right.

template<class T>
Node<T>* searchmiddle(Node<T>* left,  Node<T>* right, const T& key) {
    if (left->data == key) return left;
    if (right->data == key) return right;
    return searchmiddle(left->prev, right->next, key);   
}

template<class T>
Node<T>* searchmiddle(Node<T>* middle, const T& key) {
    return searchmiddle(middle, middle->next, key);
}

This is purely theoretical though since it'll most probably stop working when the stack is full. It also doesn't check for nullptr since the list is said to be infinite.

Nothing in the requirement says anything about printing an index so I made it return a pointer to the found Node<T> instead.