Bir dizinin yarısı nedir ve nasıl belirlenir?

Bir dizinin (veya sıralanmışsa dizinin "medyanı") yarısı, sıralanmışsa diziyi ikiye bölen, medyan veya medyan gibi bir öğedir: medyan, diziyi sıraladığınızda, diziyi ikiye ayıran ve medyan veya medyan gibi bir öğedir. Eğer öğe sayısı çift ise, medyan genellikle iki ortadaki öğenin aritmetik ortalaması olarak hesaplanır. Mülakatlarda "dizinin yarısı" bağlamında, N/2'den fazla kez görünen çoğunluk öğesinin aranması da kastedilebilir, burada N, dizideki öğe sayısıdır.

Dizinin yarısının tanımı bağlama bağlıdır:

1. Medyan (sıralanmış dizi veya k- en küçük öğeyi ararken):

   • Diziyi sıralarız.
   • Eğer N tek ise, medyan N/2 indeksindeki öğedir.
   • Eğer N çift ise, medyan N/2 - 1 ve N/2 indekslerindeki öğelerin aritmetik ortalamasıdır.

2. Çoğunluk öğesi (N/2’den fazla kez görünen):

   • Boyer oy kullanma algoritmasını kullanırız.
   • Bir candidate ve count değişkeni oluştururuz.
   • Diziyi dolaşırız. Eğer mevcut öğe candidate’a eşitse, count’u artırırız. Değilse ve count > 0 ise, count’u azaltırız. Eğer count = 0 ise, mevcut öğe yeni candidate olur ve count 1 olarak ayarlanır.
   • İlk geçişten sonra, candidate potansiyel bir çoğunluk öğesidir. Bunu doğrulamak için ikinci bir geçiş yaparız ve gerçekten N/2’den fazla kez görünüp görünmediğini kontrol ederiz.

Swift'te medyanı belirleme örneği:

// Medyanı bulmak için sıralama
func findMedian(in array: [Int]) -> Double? {
    guard !array.isEmpty else { return nil }

    let sortedArray = array.sorted()
    let n = sortedArray.count

    if n % 2 == 1 {
        return Double(sortedArray[n / 2])
    } else {
        return Double(sortedArray[n / 2 - 1] + sortedArray[n / 2]) / 2.0
    }
}

Çoğunluk öğesini belirlemek için Swift'te örnek:

// Boyer oy kullanma algoritması
func findMajorityElement(in array: [Int]) -> Int? {
    var candidate: Int? = nil
    var count = 0

    for element in array {
        if count == 0 {
            candidate = element
            count = 1
        } else if element == candidate {
            count += 1
        } else {
            count -= 1
        }
    }

    // Adayın gerçekten çoğunluk öğesi olup olmadığını kontrol et
    var realCount = 0
    if let candidate = candidate {
        for element in array {
            if element == candidate {
                realCount += 1
            }
        }
        if realCount > array.count / 2 {
            return candidate
        }
    }

    return nil // Çoğunluk öğesi yok
}

İşin doğrusu, mülakatçıyla "dizinin yarısı" ifadesinin tam olarak ne anlama geldiğini netleştirmek önemlidir.