რა არის მასივის ნახევარი და როგორ განსაზღვროთ იგი?

Մասիվի կեսը (կամ «մեդիան» մասիվի, եթե այն դասավորված է) այն տարրն է, որը, եթե մասիվը դասավորված է, բաժանում է այն երկու մասի՝ տարրեր, որոնք փոքր կամ հավասար են մեդիանին, և տարրեր, որոնք մեծ կամ հավասար են մեդիանին։ Եթե տարրերի քանակը զույգ է, մեդիան հաճախ հաշվվում է երկու կենտրոնական տարրերի միջին արժեքը։ «Մասիվի կես» հասկացությունը հարցազրույցների խնդիրներում կարող է նաև ենթադրել մաժորիտար տարր որոնելը, որը հանդիպում է ավելի քան N/2 անգամ, որտեղ N՝ մասիվի տարրերի քանակն է:

Մասիվի կեսի որոշումը կախված է կոնտեքստից՝

1. Մեդիան (դասավորված մասիվի կամ k-րդ ամենափոքր տարրն որոնելիս):

   • Դասավորում ենք մասիվը։
   • Եթե N-ը կենտ է, մեդիան այն տարրն է, որը գտնվում է N/2 ինդեքսում։
   • Եթե N-ը զույգ է, մեդիան հաշվվում է երկու կենտրոնական տարրերի միջին արժեքը։

2. Մաժորիտար տարր (նա այն, որը հանդիպում է > N/2 անգամ):

   • Օգտագործում ենք Բոյերի քվեարկության ալգորիթմը (Boyer–Moore majority vote algorithm):
   • Ստեղծում ենք candidate և count փոփոխականները։
   • Դասավորում ենք մասիվը։
   • Եթե ընթացիկ տարրն հավասար է candidate-ին, ավելացնում ենք count-ը։
   • Եթե ոչ, և count > 0, նվազեցնում ենք count-ը։
   • Եթե count = 0, ընթացիկ տարրն է դառնում նոր candidate, և count-ը վերականգնվում է 1։
   • Առաջին անցումից հետո candidate-ն կարող է լինել մաժորիտար տարր։ Անհրաժեշտ է երկրորդ անցում կատարել, որպեսզի հաստատվի, որ այն իսկապես հանդիպում է > N/2 անգամ։

Օրինակ՝ մեդիան որոշելու համար (Swift-ով):

// Դասավորում ենք մեդիան գտնելու համար
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
    }
}

Օրինակ՝ մաժորիտար տարր գտնելու համար (Swift-ով):

// Բոյերի քվեարկության ալգորիթմ
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
        }
    }

    // Ստուգում՝ արդյոք candidate-ն իսկապես մաժորիտար է
    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 // Մաժորիտար տարր չկա
}

Կարևոր է հարցազրույցի մասնակիցից ճշտել, թե կոնկրետ ինչ տեսակի «մասիվի կես»-ն է նկատի։