Majority-Element-D&C

package main

import (
    "fmt"
)

func majority(A []int, l int, r int) int {
    if l == r {
        return A[l]
    }
    mid := (l + r) / 2
    a := majority(A, mid+1, r)
    b := majority(A, l, mid)
    if a == b {
        return a
    }
    count_a := 0
    count_b := 0
    for i := l; i <= r; i++ {
        if A[i] == a {
            count_a += 1
        } else if A[i] == b {
            count_b += 1
        }
    }
    if count_a > (r-l+1)/2 {
        return a
    } else if count_b > (r-l+1)/2 {
        return b
    } else {
        return -1 // Not found
    }
}

func main() {
    A := []int{2, 2, 3, 4, 2, 2, 5}
    l := 0
    r := len(A) - 1
    result := majority(A, l, r)
    if result != -1 {
        fmt.Println("Majority element:", result)
    } else {
        fmt.Println("No majority element found.")
    }
}