C++

Forum

 
Implementing an interpolation search for a linked list, need help

Argus (9)
Write your question here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
   void List::interpolationSearch(int id){
	Node* low = head;
	Node* mid = low;
	Node* high = tail;

	int lowest = 0;
	int middle;
	int highest = getLength()-1;
	int counter = 0;

	while (low->getData()->getId() <= id && high->getData()->getId() >= id){
		middle = lowest + (id - low->getData()->getId()) * (highest - lowest) /
			(high->getData()->getId() - low->getData()->getId());
		while (middle != counter){
			mid->setSig(low);
			counter++;
			if (mid->getData()->getId() < id){
				low = mid;
			} else if (mid->getData()->getId() > id){
				high = mid;
			} else{
				cout <<"1"<<endl;
			}

			if (low->getData()->getId() == id){
				cout<<"1"<<endl;
			} else{
				cout<<"-1"<<endl;
			}
		}
	}


That's what I've got, but it is not working, it is always printing -1 even when the element is in the list. I know using this kind of search is a dumb idea for linked list, it is going to be more inefficient than a sequential search but my college professor asked for it to be done.
kbw (9488)
Write your question here.
Perhaps you should start with a question.
Topic archived. No new replies allowed.