The binary search in prev_badblocks() is correct, but it is doing excessive comparisons. Once p[hi - 1] is compared we do not have to compare it again. Also remove the if after the loop since the condition is always true; s is always greater or equal too p[lo]; on function entry, if p[lo]) > s is true we exit early, and then lo is set to mid if p[mid] < s. The first issue was found with an LLM, the second on code inspection. Signed-off-by: Sean Young --- block/badblocks.c | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) diff --git a/block/badblocks.c b/block/badblocks.c index ece64e76fe8f..143b488b7fe6 100644 --- a/block/badblocks.c +++ b/block/badblocks.c @@ -496,14 +496,14 @@ static int prev_badblocks(struct badblocks *bb, struct badblocks_context *bad, } lo = 0; - hi = bb->count; + hi = bb->count - 1; p = bb->page; /* The following bisect search might be unnecessary */ if (BB_OFFSET(p[lo]) > s) return -1; - if (BB_OFFSET(p[hi - 1]) <= s) - return hi - 1; + if (BB_OFFSET(p[hi]) <= s) + return hi; /* Do bisect search in bad table */ while (hi - lo > 1) { @@ -521,8 +521,7 @@ static int prev_badblocks(struct badblocks *bb, struct badblocks_context *bad, hi = mid; } - if (BB_OFFSET(p[lo]) <= s) - ret = lo; + ret = lo; out: return ret; } -- 2.55.0