Binary Search in ABAP

by | May 30, 2018 | ABAP Programs

Home » SAP » ABAP » ABAP Programs » Binary Search in ABAP

Preface – This post is part of the ABAP Programs series.

Binary Search in ABAP is an important topic in terms of interview question. In general, ABAP provides keyword “SEARCH” for searching purpose and that is widely used everywhere. In this article, we will learn: What is a Binary Search and how to implement it in our ABAP programs.

What is a Binary Search?

A Binary Search is a search method in which a particular value is searched from an array (in case of ABAP, Internal Table) of values via a procedure as listed below:

  1. The whole array is firstly sorted.
  2. Then the searched value is compared with the middle value.
  3. If it is equal, then output is shown with index/position of value.
  4. If it is less than the middle value, then values after middle value is discarded and if it is greater than the middle value then the values before middle value is discarded.
  5. Repeat step 4 till we achieve step 3. If it is not achieved till end then “Not Found”  message is printed on the screen. The process is shown below using image (click on the image) and program:

Binary Search

Binary Search in ABAP:

DATA : wa_data type int4,
      ITAB_data type TABLE OF int4,
      last_num type int1, " Index of Last Number
      first_num type int1 value 1, " Index of First number
      flag type int1 value 0,
      pos_length type int1.
SELECTION-SCREEN BEGIN OF SCREEN 0100 . "Where we create a Screen 0100
SELECT-OPTIONS: s_data FOR wa_data. "Seclect-Option for multiple Input
PARAMETERS: p_input type int4.
SELECTION-SCREEN END OF SCREEN 0100.
DATA: wa_sdata LIKE LINE OF s_data.
START-OF-SELECTION.
CALL SELECTION-SCREEN 0100.
  LOOP AT s_data INTO wa_sdata.
    APPEND wa_sdata-low TO ITAB_data.
  ENDLOOP.
  DESCRIBE TABLE ITAB_data LINES last_num." Here we get total number of record and currently it the index of last number
  Sort ITAB_data.
  pos_length = ( last_num ) / 2 .
  while ( first_num <= last_num ).
   READ TABLE ITAB_data INTO wa_data INDEX pos_length.
   IF ( p_input = wa_data ) .
     flag = 1.
     Exit.
     ELSEIF ( p_input < wa_data ).
       last_num =  pos_length - 1.
       pos_length = ( first_num + last_num ) / 2 .
       ELSE.
         first_num = pos_length + 1.
         pos_length = ( first_num + last_num ) / 2 .
     ENDIF.
    ENDWHILE.
   IF ( Flag = 1 ).
    Write: 'Hurray! Found  your input @ position', pos_length.
    ELSE.
      Write 'Sorry! Not Found'.
    ENDIF.
 

Explanation

In the program above, initially we have defined data types: One internal tables [to store input array of data], one work area [To be used by the above mentioned internal tabls],  one variable [to save current line/index], one variable [to store current position], one variable to be used as a flag, two variable [to store first and last variable of internal table].

We have then created a selection screen to take input and save it in an internal table. Now we will be using DESCRIBE, we will get the total number of records in that internal table. Then we will sort the internal table using “SORT” statement.

Then we use a loop and use the algorithm steps mentioned above and set a flag as 1, if data is found. And in last, print either “Found” with position of the data or “Not Found”.

Author

6 Comments

  1. SD

    This results in an endless loop if the search term is not present in the table.

    Reply
    • Abhijeet Kankani

      And this can be corrected by using last_num = pos_length – 1 and first_num = pos_length + 1 .

      Reply
  2. Abhijeet

    Hi Barry,

    Great job, appreciated.

    But when I am using list (( 9 ) ( 1 ) ( 3 ) ( 4 ) ( 8 ) ( 5 )) and want to search 2 in the given list it becomes an infinite loop.
    Thought to share with you.

    Regards,
    Abhijeet Kankani

    Reply
    • Abhijeet Kankani

      And this can be corrected by using last_num = pos_length – 1 and first_num = pos_length + 1 .

      Reply
      • Barry Allen

        Hi Abhijeet,
        Thanks for pointing it out. We will do the needful changes.

        Reply
  3. Pratik Rajni Ashani

    *&——————————-,————————————–*
    *& Report ZTEST_DEL1
    *&———————————————————————*
    *&
    *&———————————————————————*
    REPORT ztest_del1.
    PARAMETERS: p_target TYPE i.

    DATA(gt_arr) = VALUE int4_table( ( 0 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ).
    DATA(gv_target) = p_target.
    DATA(gv_begin) = 1.
    DATA(gv_end) = lines( gt_arr ).
    DATA(gv_found_index) = 1.

    PERFORM bin_search USING gt_arr
    gv_begin
    gv_end.
    *&———————————————————————*
    *& Form BIN_SEARCH
    *&———————————————————————*
    * text
    *———————————————————————-*
    * –>P_LT_ARR text
    * –>P_LV_BEGIN text
    * –>P_LV_END text
    *———————————————————————-*
    FORM bin_search USING lt_arr TYPE int4_table
    lv_begin TYPE i
    lv_end TYPE i.

    DATA(lv_mid) = lv_end – ( ( lv_end – lv_begin ) / 2 ).

    IF lv_end GE lv_begin.

    IF gv_target EQ lt_arr[ lv_mid ].
    WRITE: ‘Found at ‘, lv_mid.
    EXIT.
    ELSEIF lt_arr[ lv_mid ] GT gv_target.
    lv_begin = 1.
    lv_end = lv_mid – 1.

    PERFORM bin_search USING lt_arr lv_begin lv_end.
    ELSE.
    lv_begin = lv_mid + 1.
    lv_end = lv_end.
    PERFORM bin_search USING lt_arr lv_begin lv_end.
    ENDIF.
    ELSE.
    WRITE:’Not Found’.
    ENDIF.

    ENDFORM.

    Reply

Submit a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Author