bir vektörde ortadaki nesneyi bulmak için, neden "mid = (beg + end)/2" yerine "mid = beg + (bit - dilenmek)/2" yi kullanın.

Question

C++ 'ya yeni oldum. Bu kodu çevrimiçi olarak gördüm, bir vektör içinde bir dize bulmaya çalışıyor.

mid = (beg + end) /2 

mid = (beg + (end - 1))/2 uygulanabilir alternatif midir: Ancak, ben sağ sonuna doğru fark etmiş: olarak

mid = beg + (end - beg)/2; 

Neden bu şekilde yazılacak ilgisi var, neden yazılamaz?

Bunun nedenini anlamak için uğraşıyorum.

vector<string> text = {"apple", "beer", "cat", "dog"}; 
    string sought = "beer"; 

    auto beg = text.begin(), end = text.end(); 
    auto mid = text.begin() + (end - beg)/2; 
    while (mid != end && *mid != sought){ 
     if(sought < *mid){ 
      end = mid; 
     } else { 
      beg = mid + 1; 
     } 
     mid = beg + (end - beg)/2; 
    } 

Answer 1

Genelde ikili aramada, bunun nedeni taşmayı önlemek. beg+end, büyük değerler ile taşmaya tabidir. end-beg'u kullanmak taşmayı önler.

beg arasında hayal begin+end ise MAX_INT-3 ve end ardından beg+end, end-begin bir sayıdır çünkü bu aynı zamanda dışarı çalışır, sadece yineleyiciler 2.

olacaktır end-begMAX_INT daha büyük olurdu, ama MAX_INT-1 oldu geçerli değil. Aralarındaki mesafeyi elde etmek için iki yineleyici çıkartabilirsiniz, ancak iki yineleyici ekleyemezsiniz.

Answer 2

İki yineleyici eklemek mantıklı değildir ve bunu yapamazsınız.

İki yineleyicide operator- numaralı telefonu arayabilir ve iki yineleyici arasındaki öğelerin sayısını makul bir sonuç verir. Ve yineleyici üzerinde entegre bir sayı ekleyebilir veya çıkartabilirsiniz, ileri veya geri hareket ettirebilirsiniz. Ama iki yineleyici eklenmesi sonucu ne olmalıdır?

mid = beg + (end - beg)/2; 
      ~~~~~~~~~~  => get the count between beg and end 
      ~~~~~~~~~~~~~~~ => get the half of the count 
     ~~~~~~~~~~~~~~~~~~~~~ => get the iterator pointing to the middle position between beg and end 

mid = (beg + end) /2 
     ~~~~~~~~~ => What would the result represent?