On older maps, look for the area of Podolia. From there, if you can locate the Southern Bug River you can usually find Chornyi Ostriv. The river can be spelled Boh, Buh, or Bug, and may or may not have "Southern" or "Pivdennyi" (southern in Ukrainian) in front of it.
If you manage to locate the Southern Bug, just follow it inland, away from the Black Sea and Chornyi Ostriv is within a few miles of the river's end.
This map by Visscher, Nicolaes from 1690 shows Podolia as a Palatinate of the Polish-Lithuanian Commonwealth. The map also shows that Tarnopol (to the west of "Czarne Ostrow") was part of Podolia at that time.
Visit the David Rumsey Map Collection for a full zoomable map.
This map by Homann, Johann Baptist shows "Czarne Ostro" and "Ploskyrof", with Tarnopol to the east. This map is curious because it was made before the Russian annexation and has "Ukraina" as a designation for Podolia Superior and Podolia Inferior.
Visit the David Rumsey Map Collection for full zoomable map.
This map is from 1867 [translated in 1917], it shows 'Tschorny Ostow" on the main road going west from "Proszkurow".
Full map here.