ABAP for newbies – Importance of BINARY SEARCH (2)

[former_member571549]

Hi,

Thanks to the valuable comments of community i think i can improve the information of the previous post, i'm doing a bit of research, and i will add more tests for a next post. About the optimization of WHERE clause in LOOPs i found there's a good explanation in the official documentation about the subject: https://help.sap.com/doc/abapdocu_752_index_htm/7.52/en-us/abenitab_where_optimization.htm

Meanwhile i want to write briefly about a problem mentioned on the comments of the first post https://blogs.sap.com/2020/02/06/abap-for-newbies-importance-of-binary-search/, the use of BINARY SEARCH with an unsorted table. When performing a binary search the alghorithm starts at the middle of the table and it checks if the entry at the middle of the table is smaller or bigger than the value i'm looking for, if the entry is smaller the first half of the table can be discarded, if it's bigger the last half will be discarded, then the alghorithm is repeated with the half of the table not discarded, this procedure is done until the value i'm looking for is found. Performing this check to discard half of the data is correct only when the data is sorted.

Does not look like a big problem, we just have to use the BINARY SEARCH only on tables that were sorted. But let's test what happens when our data it's not sorted. I coded the next example:

TYPES: BEGIN OF lt_unsorted,

           number TYPE i,

         END OF lt_unsorted.



  DATA: li_unsorted TYPE STANDARD TABLE OF lt_unsorted

                    WITH HEADER LINE.



  li_unsorted-number = 1.

  APPEND li_unsorted.

  li_unsorted-number = 3.

  APPEND li_unsorted.

  li_unsorted-number = 2.

  APPEND li_unsorted.



  READ TABLE li_unsorted WITH KEY number = 2

                         BINARY SEARCH.



  WRITE: / 'SY-SUBRC is:', sy-subrc.

The output for the program is:



The program compiles ok but first thing we note from the output is that when a BINARY SEARCH is done over an unsorted table your program will most probably not work unless your READ TABLE statements are really lucky. In our example when the BINARY SEARCH algorithm is applied the entry with value 2 in the number field can't be found because the program is wrong, but you will not get any warning of this error, so if you forgot to sort the table you will have to detect it by yourself.

This is a very simple program and the solution is clear, but in big programs could be not as easy to find the problem, luckily there's a very handy option in the debugger.

To activate it follow the next steps:

1. When in the debugger go to Settings->Change Debugger Profile/Settings
   


2. Mark the "Check Sorting Before READ BINARY SEARCH" option:
   

If i run my program now i will get a dump when a BINARY SEARCH over and unsorted table is performed, i will see this kind of dump:



In the dump detail you can see exactly in which line the wrong READ was detected.

An important thing you must know is that you will get this dump only when the data is not sorted, but if you use an example where your data is sorted not intentionally but by chance, you will not get the dump because the debugger option only can check if at the moment of the READ the data it's ok, but it can't know if the correctness of data is because of a SORT or to chance.

If you suspect your program is returning wrong data because a wrong BINARY SEARCH my recommendation is to run the program with this option activated, it's faster than analyze the whole source code.

You can find full code at this github repository: https://github.com/jordirosa/ABAP4Newbies

The repository report program for this example is YJRS_ABAP_002.

I will write about the alternatives and their performance if you find it interesting and you want to be notified of the new content you can follow my profile.

Regards