Di mana saya bisa mendapatkan algoritme pencarian biner C ++ yang "berguna"?

Saya memerlukan algoritma pencarian biner yang kompatibel dengan wadah C ++ STL, seperti std::binary_searchdi <algorithm>header perpustakaan standar , tetapi saya membutuhkannya untuk mengembalikan iterator yang menunjuk pada hasil, bukan boolean sederhana yang memberi tahu saya jika elemen itu ada.

(Sebagai catatan tambahan, apa yang dipikirkan komite standar ketika mereka mendefinisikan API untuk binary_search ?!)

Perhatian utama saya di sini adalah bahwa saya memerlukan kecepatan pencarian biner, jadi meskipun saya dapat menemukan data dengan algoritme lain, seperti yang disebutkan di bawah ini, saya ingin memanfaatkan fakta bahwa data saya diurutkan untuk mendapatkan manfaat dari biner pencarian, bukan pencarian linier.

sejauh ini lower_bounddan upper_boundgagal jika datum hilang:

//lousy pseudo code
vector(1,2,3,4,6,7,8,9,0) //notice no 5
iter = lower_bound_or_upper_bound(start,end,5)
iter != 5 && iter !=end //not returning end as usual, instead it'll return 4 or 6

Catatan: Saya juga baik-baik saja menggunakan algoritme yang tidak termasuk dalam namespace std asalkan kompatibel dengan container. Seperti, katakanlah boost::binary_search,.

Tidak ada fungsi seperti itu, tetapi Anda dapat menulis yang sederhana menggunakan std::lower_bound, std::upper_boundatau std::equal_range.

Implementasi sederhana bisa jadi

template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    // Finds the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}

Solusi lain adalah menggunakan a std::set, yang menjamin pengurutan elemen dan menyediakan metode iterator find(T key)yang mengembalikan iterator ke item yang diberikan. Namun, persyaratan Anda mungkin tidak kompatibel dengan penggunaan satu set (misalnya jika Anda perlu menyimpan elemen yang sama beberapa kali).

Anda harus melihatnya std::equal_range. Ini akan mengembalikan sepasang iterator ke kisaran semua hasil.

Ada satu set di antaranya:

http://www.sgi.com/tech/stl/table_of_contents.html

Pencarian untuk:

• batas bawah
• batas_atas
• rentang_sama
• binary_search

Di catatan terpisah:

Mereka mungkin berpikir bahwa penampung penelusuran dapat menghasilkan lebih dari satu hasil. Tetapi pada kesempatan aneh di mana Anda hanya perlu menguji keberadaan versi yang dioptimalkan juga akan menyenangkan.

Jika std :: lower_bound terlalu rendah untuk Anda sukai, Anda mungkin ingin memeriksa boost :: container :: flat_multiset . Ini adalah pengganti drop-in untuk std :: multiset yang diimplementasikan sebagai vektor yang diurutkan menggunakan pencarian biner.

Implementasi terpendek, bertanya-tanya mengapa tidak disertakan dalam pustaka standar:

template<class ForwardIt, class T, class Compare=std::less<>>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={})
{
    // Note: BOTH type T and the type after ForwardIt is dereferenced 
    // must be implicitly convertible to BOTH Type1 and Type2, used in Compare. 
    // This is stricter than lower_bound requirement (see above)

    first = std::lower_bound(first, last, value, comp);
    return first != last && !comp(value, *first) ? first : last;
}

Dari https://en.cppreference.com/w/cpp/algorithm/lower_bound

Periksa fungsi ini, qBinaryFind :

RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )

Melakukan pencarian biner dari rentang [awal, akhir) dan mengembalikan posisi kemunculan nilai. Jika tidak ada kemunculan nilai, pengembalian berakhir.

Item dalam rentang [awal, akhir) harus diurutkan dalam urutan menaik; lihat qSort ().

Jika ada banyak kemunculan dengan nilai yang sama, salah satunya dapat dikembalikan. Gunakan qLowerBound () atau qUpperBound () jika Anda membutuhkan kontrol yang lebih baik.

Contoh:

QVector<int> vect;
 vect << 3 << 3 << 6 << 6 << 6 << 8;

 QVector<int>::iterator i =
         qBinaryFind(vect.begin(), vect.end(), 6);
 // i == vect.begin() + 2 (or 3 or 4)

Fungsi ini termasuk dalam <QtAlgorithms>tajuk yang merupakan bagian dari pustaka Qt .

std :: lower_bound () :)

int BinarySearch(vector<int> array,int var)
{ 
    //array should be sorted in ascending order in this case  
    int start=0;
    int end=array.size()-1;
    while(start<=end){
        int mid=(start+end)/2;
        if(array[mid]==var){
            return mid;
        }
        else if(var<array[mid]){
            end=mid-1;
        }
        else{
            start=mid+1;
        }
    }
    return 0;
}

Contoh: Misalkan sebuah array, A = [1,2,3,4,5,6,7,8,9] Misalkan Anda ingin mencari indeks 3 Awalnya, start = 0 dan end = 9-1 = 8 Sekarang , sejak awal <= akhir; pertengahan = 4; (array [mid] yaitu 5)! = 3 Sekarang, 3 terletak di kiri mid karena lebih kecil dari 5. Oleh karena itu, kita hanya mencari bagian kiri array. Oleh karena itu, sekarang start = 0 dan end = 3; mid = 2. Sejak array [mid] == 3, maka kita mendapatkan nomor yang kita cari. Karenanya, kami mengembalikan indeksnya yang sama dengan mid.

Solusi yang mengembalikan posisi di dalam rentang bisa seperti ini, hanya menggunakan operasi pada iterator (itu harus berfungsi bahkan jika iterator tidak aritmatika):

template <class InputIterator, typename T>
size_t BinarySearchPos(InputIterator first, InputIterator last, const T& val)
{       
    const InputIterator beginIt = first;
    InputIterator element = first;
    size_t p = 0;
    size_t shift = 0;
    while((first <= last)) 
    {
        p = std::distance(beginIt, first);
        size_t u = std::distance(beginIt, last);
        size_t m = p + (u-p)/2;  // overflow safe (p+u)/2
        std::advance(element, m - shift);
        shift = m;
        if(*element == val) 
            return m; // value found at position  m
        if(val > *element)
            first = element++;
        else
            last  = element--;

    }
    // if you are here the value is not present in the list, 
    // however if there are the value should be at position u
    // (here p==u)
    return p;

}