A wireless device that discovers other wireless devices for the formation of a peer-to-peer connection may perform a scan that is limited in duration and power consumption. The scan nonetheless is highly likely to discover a device, if a discoverable device exists. In addition, the scan may be performed in compliance with parameters of a peer-to-protocol such that the scan may be readily implemented in a wireless device, in some embodiments even as a firmware upgrade on a wireless network interface card. Parameters of the scan may be adjusted to increase the likelihood that, if the scan completes without discovering a device, no discoverable device exists. The scan may be used in an overall process in which discovery ends or the scan is selectively repeated following an unsuccessful scan, without entering a find phase.