stl binary_search with linked list

I have a class associated with a linked list and would like to implement the binary_search algorithm. How?

Code:

---

long s;
cout<<"Enter item to serach"<<endl;
cin>>s;

 for(iter2 = form2List.begin();iter2 != form2List.end(); iter2++)
        {
binary_search(form2List.front(),form2List.end(),(*iter2).var1,s);
        }

---

thanks..

binary_search works with random access iterators, which list does not have. You cannot do this.


Jeff

Well, you can't, or at the least it would not make sense.

If you are using a linked list, random access to an element is O(n). Now binary search relies on the fact that random access is much faster than cycling through all the elements (typically random access is O(1) for arrays).

Can't you use std::list or std::vector or maybe even std::set ?

Thank you. I will look at alternatives..

If your list is always sorted, and you need to insert / delete elements dynamically, I would definitely recommend using std::set. Internally it is implemented most of the time as a red-black tree (so that it is guaranteed to be balanced to some degree). Random access, insertion and deletion are all O(log n) and the nice thing is that it always remains sorted ;)

Thanks, I will check out std::set, as the requirements do not depend on linked list. I was only going for something quick, that would not require me to write my own structure for the porject.

std::set sounds good...