topic Re: linear search and binary search in Application Development and Automation Discussions

linear search and binary search

Former Member — Thu, 20 Dec 2007 08:58:52 GMT

can any one tell me what is linear and binary search in detail.

and what is the difference between them .

which one is useful in coding.

Thanks&Regards,

S.GangiReddy.

Re: linear search and binary search

Former Member — Thu, 20 Dec 2007 09:01:40 GMT

BINAY SEARCH in READ will definitely increase performance.But you need to SORT the internal table with all fields specifying in your READ statement.

Use the following statement before READ statement with BINARY SEARCH.

SORT TKOMV BY KNUMV KPOSN KSCHL.

READ TABLE TKOMV WITH KEY KNUMV = GT_VBAK-KNUMV

KPOSN = GT_VBAP-POSNR

KSCHL = 'PR00'

BINARY SEARCH.

binary search is one of the fastest way to find the record exists in the internal table.

TO use BINARY SEARCH, you have to SORT the internal table in ASCENDING/DESCENDING ORDER. Then only you will get the exact results.

For more detail you can refer to below threads:

If the addition BINARY SEARCH is specified, the search is binary instead of linear.

This considerably reduces the runtime of the search for larger tables (from approximately 100 entries upwards).

For the binary search, the table must be sorted by the specified search key in ascending order.

Otherwise the search will not find the correct row.

Re: linear search and binary search

Former Member — Thu, 20 Dec 2007 09:04:13 GMT

There are 9 numbers , we have to find 7

1 2 3 4 5 6 7 8 9

Linear search :

we proceed 1 by 1 : it takes 7 iterations

Binary search:

we take middle value( 5) compare with 7 now we are left with

6 7 8 9

we compare (8) and (7) with 7 ...

Thus process completed in 2 iteraions

read table itab into wa with key <> binary search.

table should be in asc order

Re: linear search and binary search

Former Member — Thu, 20 Dec 2007 09:04:15 GMT

Hi,

linear search is nothing but processing sequntially

one by one

binary search

Binary search helps incase of standard tables..where you have to sort the internal table with the field and use that field to search the internal table with binary search..

Re: linear search and binary search

Former Member — Thu, 20 Dec 2007 09:08:15 GMT

Hi,

Linear search:

Which will search line by line.

Binary Search:

which will directly go to n1/2 record if it matchs the condition then ok otherwise if the N1/2 record is greater than the searching value it will ignores the 2nd half of the records, again from the rest of 1st half records it will calculate the middle record and then it will checks for the condition, in this way it will work, it means at a single iteration it will eliminates half of the records from the search criteria.

Note:- for binary search the table should be in Sorted (ASCENDING) order.

Reward if useful.

Thanks,

Sreeram.

Re: linear search and binary search

Former Member — Thu, 20 Dec 2007 09:13:49 GMT

hi,

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.

Linear search use sequential search means each and every reord will be searched to find. so it is slow.

Binary search uses logrim for searching. Itab MUST be sorted on KEY fields fro binary search. so it is very fast.

The search takes place as follows for the individual table types :

standard tables are subject to a linear search. If the addition BINARY SEARCH is specified, the search is binary instead of linear. This considerably reduces the runtime of the search for larger tables (from approximately 100 entries upwards). For the binary search, the table must be sorted by the specified search key in ascending order. Otherwise the search will not find the correct row.

sorted tables are subject to a binary search if the specified search key is or includes a starting field of the table key. Otherwise it is linear. The addition BINARY SEARCH can be specified for sorted tables, but has no effect.

For hashed tables, the hash algorithm is used if the specified search key includes the table key. Otherwise the search is linear. The addition BINARY SEARCH is not permitted for hashed tables.

Binary search must be preffered over linear sarch.

Hope this is helpful, Do reward.

Re: linear search and binary search

Former Member — Thu, 20 Dec 2007 10:21:49 GMT

Hi,

Linear Search: : This is sequential search.

for example: we have 4 sales doc numbers like

500001

500012

501234

514444

in the above list we have to found '501234'.

so linear search will start search from 500001 next 500012

next 501234.

Binary Search: It will follow the different mechanism.

First it will make the list '1/2'.

It means it will break the list into two parts.

If the element is found in the first part. Number of repitions are less.

So use of binary search is better.

Thanks,

Anil

Re: linear search and binary search

Former Member — Thu, 20 Dec 2007 12:27:52 GMT

thanks a lot for giving wondraful example.

Thanks&Regards,

S.Gangi Reddy.