The latter; there is no need for two loops. You could replace
DO WHILE (j .GT. 0 .AND. sorted_array(j) .LT. key)
by
DO WHILE (j .GT. 0)
if ( sorted_array(j) .GE. key) exit
The latter; there is no need for two loops. You could replace
DO WHILE (j .GT. 0 .AND. sorted_array(j) .LT. key)
by
DO WHILE (j .GT. 0)
if ( sorted_array(j) .GE. key) exit