配列についてなんですが

2000個の配列の中に数値はランダムで
0~50000までが降順で数値が入っています。
a[0]=32
a[1]=501
a[2]=809
a[3]=2320
※2000個配列要素の中身はランダムで数値決定されて
そのあとに降順でソートされているとします。

入力された数値によって配列の中からその数値を越えた配列要素を
一個だけ探したいのですが

例
300だったらa[1]=501を返却したい。
総当りで求めると時間がかかるので総当り以外で
なにか方法ってないものなんでしょうか？