Cardiac computed tomography (CT) is the primary noninvasive imaging modality to diagnose coronary artery disease. Though various methods have been proposed for coronary artery segmentation, most rely on at least one user click to provide a seed point for initialization. Automatic detection of the coronary ostia (where coronaries originate from the aorta), including both the native coronary ostia and graft ostia of the bypass coronaries, can make the whole coronary exam workflow fully automatic, therefore increasing a physician's throughput. Anatomical structures (native coronary ostia) and pathological structures (graft ostia) often require significantly different detection methods. The native coronary ostia are well constrained by the surrounding structures, therefore are detected as a global object. Detecting the graft ostia is far more difficult due to the large variation in graft position. A new searching strategy is proposed to efficiently guide the focus of analysis and, at the same time, reduce the false positive detections. Since the bypass coronaries are grafted on the ascending aorta surface, the ascending aorta is first segmented to constrain the search. The quantitative prior distribution of the graft ostia on the aorta surface is learned from a training set to significantly reduce the searching space further. Efficient local image features are extracted around each candidate point on the aorta surface to train a detector. The proposed method is computationally efficient, taking about 0.40 seconds to detect both native and graft ostia in a volume with around 512 x 512 x 200 voxels.