Array_set membership

The Array_set operation contains() tests whether an Array_set contains an element with a given value. If such an element exists, contains() returns a pointer to it; otherwise, it returns zero. We can implement contains() easily using the Array Algorithm bin_search(), described in bin_search(C++):

        const T* contains(const T& t)const{
           check();
           return bin_search(t,&b[0],&b[n]);
       }

bin_search() performs a binary search on a sorted array. Unlike bin_loc(), which does a binary search to find where a given value belongs if it is not present, bin_search() searches for the element itself and returns its location if the element is found and zero otherwise. Note that because contains() does not modify any of the representation variables, we only need to check the invariant on entry.