topic Re: Binary Search in Application Development and Automation Discussions

Binary Search

Former Member — Wed, 08 Apr 2009 05:42:12 GMT

Hello,

I had a small query , its regarding read table with binary search.

My query is can we use read table with binary search on an internal table that has been sorted in descending order?

Thanks,

Alok.

Re: Binary Search

Former Member — Wed, 08 Apr 2009 05:44:00 GMT

It can be used....

But it would cause extremely Severe performance issues...better to avoid...

Re: Binary Search

Former Member — Wed, 08 Apr 2009 05:47:47 GMT

Hi SubZero,

I tried using it with descending , but it doesnt give the same results, is it that only ascending works?

and what would be the kind of performance issues incase of descending.

Thanks,

Alok.

Edited by: Alok Navare on Apr 8, 2009 7:47 AM

Re: Binary Search

Peranandam — Wed, 08 Apr 2009 05:48:35 GMT

HI ,

yes, the fields you are using with key addition in read statement shoud be in sort (it must be sorted in ascending order)

you need to sort fiels which are using with key addition

ex.

itab having fiels a, b,c ,d, e , f, g.

here you are goint to read based on three fieds a, b, c.

sort itab by a b c.

read table itab with key a = 'aaa'

b = 'bbbb'

c = 'ccc'

binary search.

Regards,

Peranandam

Edited by: peranandam chinnathambi on Apr 8, 2009 7:49 AM

Edited by: peranandam chinnathambi on Apr 8, 2009 8:21 AM

Re: Binary Search

faisalatsap — Wed, 08 Apr 2009 05:58:11 GMT

Hi, Alok,

You must Sort your Internal Table in ASCENDING order for BINARY SEARCH

Best Regards,

Faisal

Re: Binary Search

Former Member — Wed, 08 Apr 2009 05:59:15 GMT

Alok

Well the binary search algorithm itself asks for the keys to be sorted in ascending order... So it doesnt necessarily depend whether its ABAP or C or java..whatever....

I am not sure how it affects .. but i think when sorted in ascending order, performance is O(n) and when in descending order its of O(n square )......

But if its not working when its sorted in descending , then no point in using it buddy

Re: Binary Search

Former Member — Wed, 08 Apr 2009 05:59:56 GMT

Hi,

We can use for ascending and decending.

if u r getting different values means, The internal table may have multiple records with the key u r passing , If the table has only one record then the result will be same..

Performwnce is also same in both the cases..

Kiran

Edited by: kiran vempati on Apr 8, 2009 8:00 AM

Re: Binary Search

Former Member — Wed, 08 Apr 2009 06:02:01 GMT

data: itab like standard table of spfli,
      fs type spfli.

      select * from spfli into table itab.

sort itab by carrid descending .        

read table itab into fs with key carrid = 'AA' binary search.

write : fs-connid.

sort itab by carrid.        

read table itab into fs with key carrid = 'AA' binary search.

write : fs-connid.

Check the difference of the result beacuse binary search will only work with ascending sort order.

Binary search works on Divide and Rule methods. after dividing It will check with the middle value if its lesser than the searched element than it goes to right half else it goes to left half.

Hence its mandt that the search filed of the table should be in Ascending order.

Regards,

Gurpreet

Re: Binary Search

faisalatsap — Wed, 08 Apr 2009 06:03:12 GMT

Sorry, Kiran

It must be ascending order test the following code it is not working with DESCENDING but will work when Chang to ASCENDING.

TYPES: BEGIN OF ty_test,
  no TYPE i,
  END OF ty_test.
DATA: it TYPE STANDARD TABLE OF ty_test WITH HEADER LINE.

DO 1000 TIMES.
  it-no = sy-index.
  APPEND it.
ENDDO.

SORT it BY no DESCENDING.

READ TABLE it WITH KEY no = 838 BINARY SEARCH.
IF sy-subrc EQ 0.
  WRITE: it-no.
ENDIF.

Best Regards,

Faisal

Re: Binary Search

Former Member — Wed, 08 Apr 2009 06:07:16 GMT

Thanks Faisal,

U r correct... Sorry for my wrong answer...

Re: Binary Search

Former Member — Wed, 08 Apr 2009 06:11:02 GMT

If you are using the Binary search in Read statement you should sort the internal table before read statement. Otherwise it won't give correct answer.

Regards,

Joan