Randomized algorithm for 2kCNF satisfiability problem
The analysis of Schöning's algorithm (see for example these CMU lecture notes) relies on the fact that if $\alpha$ is a satisfying assignment, $\beta$ is any assignment, and $C$ is an unsatisfied $k$-clause, then flipping a random variable decreases the distance between $\beta$ and $\alpha$ with probability at least $1/k$. In your case, you can get a better guarantee since $\alpha$ satisfies half the literals in every clause.