Majority-Element-D&C

import java.util.ArrayList;
import java.util.List;

public class MajorityElement {
    public static int majority(List<Integer> A, int l, int r) {
        if (l == r) {
            return A.get(l);
        }
        int mid = (l + r) / 2;
        int a = majority(A, mid + 1, r);
        int b = majority(A, l, mid);
        if (a == b) {
            return a;
        }
        int count_a = 0;
        int count_b = 0;
        for (int i = l; i <= r; i++) {
            if (A.get(i) == a) {
                count_a += 1;
            } else if (A.get(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
        }
    }

    public static void main(String[] args) {
        List<Integer> A = new ArrayList<>();
        A.add(2);
        A.add(2);
        A.add(3);
        A.add(4);
        A.add(2);
        A.add(2);
        A.add(5);
        int l = 0;
        int r = A.size() - 1;
        int result = majority(A, l, r);
        if (result != -1) {
            System.out.println("Majority element: " + result);
        } else {
            System.out.println("No majority element found.");
        }
    }
}