topic Re: binary search in Application Development and Automation Discussions

binary search

Former Member — Sun, 11 Mar 2007 17:19:48 GMT

can anyone explain abt binary search?

Re: binary search

abdul_hakim — Sun, 11 Mar 2007 17:46:17 GMT

Hi,

Let us say u have an internal table with the following records..

Carrier ID Destination Airport

AU Australia

LH USA

LH Frankfurt

LH Australia

SQ Singapore

Suppose you have stored these records in a standard table then when you are processing the record through LOOP AT or READ TABLE statement then the system will use the table scan ie. searching the table line by line for the requested record...

For instance if you are using LOOP AT itab INTO wa WHERE carrid = 'LH'.

If your table is a standard table then system will first search first record to check whether the Carrier id is equal to LH if not it proceed with the next reoord.

If your table is a sorted table then the system will use the binary search ie it will search only the below records..

LH USA

LH Frankfurt

LH Australia

Note you could also achive the BINARY SEARCH effect in the standard table..For that sort your standard table based on the search key and use BINARY SEARCH addition to your READ statement.

Hope this clear your doubt..

Regards,

Hakim

Mark all useful answers..

Re: binary search

Former Member — Sun, 11 Mar 2007 17:47:57 GMT

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> 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.

BINARY SEARCH approaches the middle entry in the table, decides if it matches, or lexically greater than or equal to the key being searched. It accordingly skips either the top or bottom part of the internal table and searches the other half. It repeats this process till it finds the row.

Using BINARY SEARCH with READ is the most efficient way to read standard internal tables which are sorted by the key used to search them

BINARY SEARCH addition when reading a sorted table is not required, as it happens by default. It makes a good difference in performance if you are reading a large standard internal table without sorting and reading by BINARY SEARCH

Best regards,

Vishnu T

Re: binary search

kiran_k8 — Mon, 12 Mar 2007 03:39:52 GMT

Chaitanya,

I will try to put it in a simple way.

for ex:-

if we have the following numbers

10,20,30,40,50,60,70.

Now think that we are searching for a number 30.

when we use a binary search it will split the entire data into two halfs and first search in the first half.

I mean to say it will for 30 among 10,20,30,40.

So it will find the number we are searching for and thus avoids the unnecessary search in the remaining half.Thus it improves performance.

If the number is not found in that then it will continue with searching the 2nd half.

K.Kiran

Re: binary search

Former Member — Mon, 12 Mar 2007 03:45:00 GMT

some morte additional info......

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.

Re: binary search

Former Member — Mon, 12 Mar 2007 03:46:56 GMT

good

Use of binary search option

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.

thanks

mrutyun^

Re: binary search

Former Member — Mon, 12 Mar 2007 04:52:41 GMT

HI ,

Binary serach is a quicker way to read record in an internal table .

Please note that when ever you use BINARY SERACH..

sort the table based on the requirement and while using BINARY SERACH use with the keys on ehich table is sorted .

Thanks .

Re: binary search

Former Member — Mon, 12 Mar 2007 05:14:13 GMT

Hi,

In addition to our forumates info... I am here adding a bit to that.

b4 you use binery search.. dont forget to sort the internal table.

if not sorted and used binary search mens.. u will not find the specified record in most of the cases, even its present in the table.

Regards,

Sujatha.