Binary Search

[Former Member]

Hi,

I Need some inputs about binary search.

1. Why we should go to bianry search?

2. When the binary search will use in real time?

3. Explain with real time example?

[Former Member]

Check the following Document

http://help.sap.com/saphelp_erp2005/helpdata/en/fc/eb35de358411d1829f0000e829fbfe/frameset.htm

/people/harry.dietz/blog/2005/10/28/performance-improvement-hints-3-internal-table--fill-and-read

Standard Internal Tables

Standard tables have a linear index. You can access them using either the index or the key. If you use the key, the response time is in linear relationship to the number of table entries. The key of a standard table is always non-unique, and you may not include any specification for the uniqueness in the table definition.

This table type is particularly appropriate if you want to address individual table entries using the index. This is the quickest way to access table entries. To fill a standard table, append lines using the (APPEND) statement. You should read, modify and delete lines by referring to the index (INDEX option with the relevant ABAP command). The response time for accessing a standard table is in linear relation to the number of table entries. If you need to use key access, standard tables are appropriate if you can fill and process the table in separate steps. For example, you can fill a standard table by appending records and then sort it. If you then use key access with the binary search option (BINARY), the response time is in logarithmic relation to

the number of table entries.

Sorted Internal Tables

Sorted tables are always saved correctly sorted by key. They also have a linear key, and, like standard tables, you can access them using either the table index or the key. When you use the key, the response time is in logarithmic relationship to the number of table entries, since the system uses a binary search. The key of a sorted table can be either unique, or non-unique, and you must specify either UNIQUE or NON-UNIQUE in the table definition. Standard tables and sorted tables both belong to the generic group index tables.

This table type is particularly suitable if you want the table to be sorted while you are still adding entries to it. You fill the table using the (INSERT) statement, according to the sort sequence defined in the table key. Table entries that do not fit are recognised before they are inserted. The response time for access using the key is in logarithmic relation to the number of

table entries, since the system automatically uses a binary search. Sorted tables are appropriate for partially sequential processing in a LOOP, as long as the WHERE condition contains the beginning of the table key.

Hashed Internal Tables

Hashes tables have no internal linear index. You can only access hashed tables by specifying the key. The response time is constant, regardless of the number of table entries, since the search uses a hash algorithm. The key of a hashed table must be unique, and you must specify UNIQUE in the table definition.

This table type is particularly suitable if you want mainly to use key access for table entries. You cannot access hashed tables using the index. When you use key access, the response time remains constant, regardless of the number of table entries. As with database tables, the key of a hashed table is always unique. Hashed tables are therefore a useful way of constructing and

using internal tables that are similar to database tables.

the prerequisite for a binary search on an internal table is it should be sorted.

READ TABLE itab WITH KEY k1 = v1 ... kn = vn

[BINARY SEARCH] [additions].

Effect

The system evaluates the specified key to identify the correct line. If the type of a value is not compatible with the type of the corresponding key field, the system uses MOVE logic to convert the value into the type of the component before reading the table. This is an asymmetric comparison logic, in which the component type takes precedence over the value type.

The way in which the system looks for an entry in the table depends on its table type. The system optimizeds the key access whenever possible

/people/harry.dietz/blog/2005/10/28/performance-improvement-hints-3-internal-table--fill-and-read

Standard Internal Tables

SORTED TABLE:

If the specified key fields form a left-justified extract of the table key or are identical with the entire table key, the search is binary, otherwise sequential.

***************************************************

If you read entries from standard tables using a key other than the default key, you can use a binary search instead of the normal linear search. To do this, include the addition BINARY SEARCH in the corresponding READ statements.

READ TABLE <itab> WITH KEY <k1> = <f1>... <kn> = <fn> <result>

BINARY SEARCH.

The standard table must be sorted in ascending order by the specified search key. The BINARY SEARCH addition means that you can access an entry in a standard table by its key as quickly as you would be able to in a sorted table.

REPORT demo_int_tables_read_index_bin.

DATA: BEGIN OF line,

col1 TYPE i,

col2 TYPE i,

END OF line.

DATA itab LIKE STANDARD TABLE OF line.

DO 4 TIMES.

line-col1 = sy-index.

line-col2 = sy-index ** 2.

APPEND line TO itab.

ENDDO.

SORT itab BY col2.

READ TABLE itab WITH KEY col2 = 16 INTO line BINARY SEARCH.

WRITE: 'SY-SUBRC =', sy-subrc.

The output is:

SY-SUBRC = 0

The program fills a standard table with a list of square numbers and sorts them into ascending order by field COL2. The READ statement uses a binary search to look for and find the line in the table where COL2 has the value 16.

*******************************************

It is used in READ TABLE statements when accessing internal tables. IF the int table is sorted by a key, then when BINARY SEARCH is added to a WITH KEY statement... the "read" to the int table is performed at a binary level for maximum performance.

*********************************************

When a programmer uses the read command, the table is sequentially searched. This slows down the processing. Instead of this, use the binary search addition. The binary search algorithm helps faster search of a value in an internal table. It is advisable to sort the internal table before doing a binary search. Binary search repeatedly divides the search interval in half. If the value to be searched is less than the item in the middle of the interval, the search is narrowed to the lower half, otherwise the search is narrowed to the upper half.

Not Recommended

Read table int_fligh with key airln = ‘LF’.

Recommended

Read table int_fligh with key airln = ‘LF’ binary search.

*********************************************

Regards

vasu

[Former Member]

Binary search reduces the amount of time when searching for records in internal table.

Before using binary search, be sure to sort your table first.

Binary search does not look for records from 1 to n of your internal table. It divides the table by two and look for the ranges where your value is residing

ex.

1

2

3

4

5

6

7

8

you're looking for 7

Binary search will do this:

Divide the content of the table into two

1234, 5678

search for the value 7, and is located in 5678

and so on....

this is more faster than searching from 1 to 8.

[Former Member]

Very good example, it is easy to understand.

[Former Member]

Hi,

When a programmer uses the read command, the table is sequentially searched. This slows down the processing. Instead of this, use the binary search addition. The binary search algorithm helps faster search of a value in an internal table. It is advisable to sort the internal table before doing a binary search. Binary search repeatedly divides the search interval in half. If the value to be searched is less than the item in the middle of the interval, the search is narrowed to the lower half, otherwise the search is narrowed to the upper half.

Not Recommended

Read table t_ekko with key airln = ‘LF’.

Recommended

Read table t_ekko with key ebeln = wa_ekko-ekorg binary search.

Reward points if useful...

-Umesh

[Former Member]

Hi,

when ever you read an internal table having more entries , better to use binary search addition.

sort table with the same key as in Read before using the same.