How else could I implement this?

[packetpirate]

I'm trying to design a search function for my linked list class called find(). So far, if the list's size is less than or equal to 50, it uses a simple sequential search. If it's greater, it searches using a recursive "binary search". I put that in quotes because it's not a TRUE binary search, but it's similar. I just want to know other ways I could implement my "binary search" or make it faster / more like a real binary search. If you need more information, just ask...

/*
* Returns the position of "n" in the list if it exists.
* Determines search method based on size of list.
* Returns 0 if search term is not found.
*/
template< typename T >
int LinkedList<T>::find(T n) {
    if(size <= 50) { // Sequential search.
        node<T> *current;
        int i = 0;

        for(current = first;current != NULL;current = current->next) {
            if(current->data == n) {
                return i;
            }
            i++;
        }
    } else {
        node<T> *current;
        node<T> *result;
        int i = 0;

        for(current = first;current != NULL;current = current->next) {
            if(i == (size/2)) {
                result = binSearch(current, n);
            }
            i++;
        }

        i = 0;

        for(current = first;current != NULL;current = current->next) {
            if(current == result) {
                return i;
            }
            i++;
        }
    }
    return 0;
}
/*
* Binary Search function that returns the index of a search term.
* Returns NULL if term is not found.
*/
template< typename T >
node<T> *LinkedList<T>::binSearch(node<T> *start, T key) {
    if(start->data == key) {
        return start;
    } else if(start->data > key) {
        return binSearch(start->prev, key);
    } else if(start->data < key) {
        return binSearch(start->next, key);
    } else {
        return NULL;
    }
}

[writetonsharma]

This is not near a binary search. This is just a sequential search with recursion.

If the linklist is sorted, than this will always move forward and this condition will never execute:

else if(start->data > key) {
        return binSearch(start->prev, key);

In case, the list is not sorted, than for example, in a list 4-2-3-5-7-6
if you have to find 2, this will crash as for the very first element it will try go back which will be null.

Edit: link list's are traversed sequentially only as the addresses are not continuous.

[packetpirate]

I said from the beginning that this wasn't a binary search...
Also, yes that condition will execute. This search is meant to run only on a sorted list.

Say I have the list: 4 5 6 7 8 9 10... that's 7 elements.
From the first FOR loop, it will set the starting position at 3 (7/2).
So the first element for comparison is 6. Let's say we're searching for 9.

if(start->data == key) // false
if(start->data > key) // 6 is not greater than 9, false
if(start->data < key) // True... 6 is less than 9.
    return binSearch(start->next, key) // Since 6 is less than 9, 9 must be higher in the list... so go to the next position. 

I think you misunderstood what the "start" pointer is for. It doesn't point to the first element in the list. It's the starting position for the search, which is the middle element in the list.

I know I have to add checks to see if the previous or next node is NULL, but I just wanted to make sure this method would work.

[D80DSL3A]

I agree with writeonsharma that you are performing a sequential search because your binSearch() still iterates through the list node by node. For a binary search your function would have to jump straight to the node in the middle of a sublist (eg; from midpoint to 1/4 or 3/4 point).

Your idea of starting at the middle of the list and searching forward or back from there seems like it could cut the # of nodes to be searched in half, except that you had to find that midpoint node* by iterating to it from the beginning - so there goes the savings.

The only idea I've had for performing a "binary like" search on a list is to maintain an array (or list) of pointers to various spots in the list like midpoint, 1/4 point, etc, or maybe a pointer to every 10th node. This searching list could be built and maintained while inserting values into the primary list.

I haven't tried it though because if a binary search able list is needed then other data structures, such as the binary search tree (BST) already exist for this.
Why not try your hand at creating a BST list?

[packetpirate]

Could you provide links with a tutorial on how?

[D80DSL3A]

I found the wikipedia articles to be adequate for a good start.
http://en.wikipedia.org/wiki/Binary_search_tree

[packetpirate]

Looking at the Python implementation, it looks almost identical to what I wrote...

[D80DSL3A]

The search function? Yes it does.
There's quite a difference in how the node*'s are used though. In a link list the node*'s point forward and back - in a line.
In a binary tree BOTH of the node*'s (left and right) point forward, but in different directions.
The list splits at each node forming a tree rather than a chained list and this makes it fundamentally different.
I've written only a very simple implementation for it myself. I'm finding that some of the concepts are quite challenging (hard). I have so far got only an unbalanced tree, but I can traverse it in order.
Recursive methods seem to be natural for use on a binary tree.

[writetonsharma]

It's the starting position for the search, which is the middle element in the list.

And how you will find the middle element of the list? through iterating sequentially if I am correct. Now this iteration is just waste as you are not keeping any information while you go till the middle of the list. Now lets say the node which you are looking may be in the first half of the list, which you could have found while finding the middle element. You will go again backward to find it.

as fun2code said, it can be helpful if you keep a supporting data structure which may speed up things.