Binary search - pytanie

Question

Wiecie może jak zaimplementować binary searcha, który bierze x lub mniejszą wartość jeśli nie ma x w ciągu. Ale gdy jest x to bierze ostatnią wystąpioną wartość?
1 3 5 10 10

odpowiedzią dla x = 10 będzie indeks (zaczynamy od 0) 4.

Answer 1

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> nums{ 1, 3, 5, 10, 10 };
    auto it = std::upper_bound(nums.begin(), nums.end(), 10);
    auto idx = std::distance(nums.begin(), it) - 1;
    std::cout << idx  << "\n";
}

Comments

Nie masz co zakładać, pomyśl chwile, rozrysuj sobie na kartce przykłady.

---

Cześć, napisałem coś takiego. Myślisz, że jest git? Gdy go testowałem to wszystko wychodziło dobrze, ale mogłem coś przeoczyć.

int l=-1,r=array.size();
        while(r - l > 1){
            int mid = l + (r - l) / 2;
            if(array[mid] <= x)
                l = mid;
            else
                r = mid-1;
        }
        cout << l << ' ';

 

---

Wygląda git, tylko ja bym zamiast r = mid-1 pisał r = mid. Chyba, że masz jakiś powód, żeby pisać r = mid-1?

---

A tylko nie dałeś if-a. w sensie przed cout << l << ' ', możesz dać:
 

if (l == -1)
   cout << "NIE ZNALAZLEM";
else
     cout << l;

 

 

 

 

---

I właśnie po to dajesz l = -1, żeby móc zrobić tego if-a, bo zauważ, że jeśli l = -1, to żaden element nie spełnia!

Właśnie dlatego ta metoda jest taka fajna, bo jeden if starcza, żeby sprawdzić, czy żaden nie spełnia.