The one nullable gotcha with doing this is that the .NET standard library doesn't have nullable annotations in older frameworks.
One approach to adding nullable annotations to a large code-base is to go "bottom-up" on DLL at a time. The annotations are somewhat viral; if you were to go top-down then as you get to more of the "shared" DLLs and add annotations you'll find yourself having to go back and revisit the DLLs you already migrated. In this light, the .NET standard library situation is problematic.
Imagine implementing IEnumerable<T> by wrapping another IEnumerable<T>; in .NET framework there are no nullable annotations, so you can get into a situation where you don't add a nullable annotation where you will eventually need one upgrading to newer .NET. This can bubble up throughout your code base, making that eventual .NET upgrade more challenging.
I'm not saying its not worth it to do this in .NET framework, but you can very easily add extra work to the inevitable(?) update to .NET 8+. When you get there you could of course temporarily regress and turn nullable stuff back to warnings until you work through that surprise backlog, but nullable is really nice so you might be strongly inclined to not do that... not a huge problem, just something to be aware of!
I highly recommend SF. The trick is you must use the books via coqIDE or something equivalent; viewing the rendered HTML is almost pointless at best, but probably counter-productive.
Binary search would be a good exercise. I think SF volume 1 would be more than enough, with the exception of deciding how to model arrays (you'd probably want to look up Coq's persistent arrays/PArray system for this.) SF volume 3 does binary search _trees_ which is similar but avoids the array problem (as is customary in functional languages.)
However, Coq (by default) also uses infinite precision numbers. This works very well for proofs but isn't necessarily realistic. This is where some extra fun comes in: fixed precision arithmetic is a very common source of bugs for binary search: https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
Some examples from a Software Foundations (a series of books about Coq, available online):
I just wrote something I called insertion sort. I want to know that this is a valid implementation of sorting. What does it mean to be a sorting algorithm? It means that the output is sorted, and it's a permutation (shuffling) of the input. This is an exercise here: https://softwarefoundations.cis.upenn.edu/vfa-current/Sort.h...
One more: say you have specified a programming language, which includes describing the structure of programs (the grammar essentially) and "small step" semantics (e.g `if true then x else y` can take a step to `x`). It would be interesting to show that any well-typed halting program can be evaluated in multiple steps to exactly one value (i.e. the language is deterministic and "doesn't get stuck" (or, in a sense, have undefined behaviour)). That's the subject of volume 2 https://softwarefoundations.cis.upenn.edu/plf-current/toc.ht... Beyond this, you may have done a similar thing for a lower level language (machine assembly, wasm, ...) and have a compiler from your language to the low level language. You may want to prove that the compiler "preserves" something, e.g. the compiled output evaluates to the same result ultimately.
RE: termination, in something like Coq that is a bit special because every function terminates by construction. That might sound limiting but it's not really/there are ways around it. It would, however, be impossible to write something like the Collatz function in Coq and extract it in the obvious sense.
EDIT: and there are other ways these tools can (theoretically) be used to work with programs, but that's a long story. There have been real-world programs built like this, but it is very uncommon at this time. It is an area of active research.