Let X be a K3 surface with Picard group Pic (X)≅ Z H such that H 2= 2 n. Let M H (v) be the moduli space of Gieseker semistable sheaves on X with Mukai vector v. We say that v satisfies weak Brill-Noether if the general sheaf in M H (v) has at most one nonzero cohomology group. We show that given any rank r≥ 2, there are only finitely many Mukai vectors of rank r on K3 surfaces of Picard rank one where weak Brill-Noether fails. We give an algorithm for finding the potential counterexamples and classify all such counterexamples up to rank 20 explicitly. Moreover, in each of these cases we calculate the cohomology of the general sheaf. Given r, we give sharp bounds on n, d, and a that guarantee that v satisfies weak Brill-Noether. As a corollary, we obtain another proof of the classification of Ulrich bundles on K3 surfaces of Picard rank one. In addition, we discuss the question of when the general sheaf in M H (v) is globally generated. Our techniques make crucial use of Bridgeland stability conditions.