You should use a SORTED table for preference. But if you have to use a standard table, then if you read the documentation about BINARY SEARCH, you'll see it only applies to ascending orders.
"I thought this should work, but it's failing."
What's exactly your problem? The following is working perfectly fine:
DATA(rnd) = cl_abap_random_int=>create( seed = + sy-uzeit min = 1 max = 100 ).
DATA: BEGIN OF line, a TYPE i, b TYPE i, c TYPE i, d TYPE i, END OF line, itab LIKE TABLE OF line WITH EMPTY KEY.
DO 10000 TIMES. itab = VALUE #( BASE itab ( a = rnd->get_next( ) b = rnd->get_next( ) c = rnd->get_next( ) d = rnd->get_next( ) ) ). ENDDO.
SORT itab BY a b ASCENDING c d DESCENDING.
READ TABLE itab INTO DATA(wa) WITH KEY a = 10 b = 10 BINARY SEARCH.
BREAK-POINT.
In addition to ABAP documentation, you can find some information about binary search in this ancient blog. Hopefully it'll make it clear.
TCODE - ABAPDOCU says ...
The addition BINARY SEARCH produces a binary search of the table, not linear. In the case of large tables (from approximately 100 entries), this can significantly reduce runtime. The table must, however, be sorted in ascending order by the components specified in the search key. The priority of the sort order must match exactly the order of the components in the search key. If this requirement is not met, the correct row is not usually found.
Add comment