Bir ön sıralanmış bir dizi belirli bir değerin endeksi bulma

4 Cevap php

Bugün, ben bir görüşme için gittim ve görüşmeyi ben böyle bir ön-sıralanmış diziye verilen bir değer (sayı) endeksi bulmak nasıl bana sordu:

$preSortedArr=array(23,32,36,41,45,54);

O da özyineleme kullanarak izin olmadığını söyledi.

Ben işlevi bu gibi bakmak gerektiğini düşünüyorum:

function findIndexByValue($preSortedArray,$value){            
//some codes here       
}

Ne çözüm benden bekliyordum düşünüyorsunuz?

EDIT: Üzgünüm, ben o ilk pseudocode yazmamı istedi eklemek unuttum, ama ben bilmiyordum dedi. Sonra PHP yazmak için çalıştım, ama o bir dilden bağımsız çözüm bekliyor düşünüyorum.

4 Cevap

O dizi ön kriteri söyledi yana, muhtemelen bir ikili arama bekliyordum. (Dizi sıralanır beri olası bir optimizasyon - yetmezliği ile çıkış daha büyük bir değer bulursanız) Bir doğrusal arama tabii örnekte küçük dizide gayet iyi olurdu. Muhtemelen daha hızlı, bu konularda.

O büyük olasılıkla arıyordu

EDIT The question is somewhat odd for the given array. There is no point in doing this with anything else than PHP's native function. An alternative would be to use while, next, key ve current elle bunu istemişti. Görüşmeci özyineleme kullanamaz kaydetti neden hala açıklamak olmaz.

Muhtemelen herhangi bir cevap arıyor değildi. Muhtemelen sizce nasıl görmek ve farklı seçenekler dikkate almak istedim, ve bir şey uygulanmasının yolunu seçmeden önce, kendi artılarını ve eksilerini explaing.

En iyi yaklaşım kullanmak için Binary search algorithm. En kötü durum karmaşıklığı o olduğunu (logn)

etiketler