BINARY SEARCH ASC or DESC ?

[former_member204618]

Dear Experts,

Does it matter how the table is sorted to use a binary search ?

If I have a table and sort by the first asc and the second desc will the search pick the 1st record it finds or will it pick the 1st record of the list that matches the key ?

Thanks

Craig

[Former Member]

Hi,

For binary search it should be always be sorted in ASCENDING..

It will pick the record that matches the key..

Thanks,

Naren

[former_member204618]

Naren,

Thanks for your answer, however I am talking about shadow tables where they all match the key and have multiple records! I am descending on the changetime field to pick the latest record.

Is this still valid ?

i.e.

SORT gt_icsclaim_des BY changetime DESCENDING.

READ TABLE gt_icsclaim_des INTO gs_icsclaim_des

WITH KEY active = ls_claim-active

claim = ls_claim-claim.

Thanks

Craig

[Former Member]

Hi,

<b>Binary search DOES NOT</b> work for ITAB if the fields are in DESCENDING Order. check the link given by me above,to understand how BINARY SEARCH WORKS.

Regards

srikanth

[Former Member]

A binary search returns the first record it finds, so if you:

SORT gt_icsclaim_des BY active claim ASCENDING changetime DESCENDING.

READ TABLE gt_icsclaim_des
  INTO gs_icsclaim_des
  WITH KEY active = ls_claim-active
           claim  = ls_claim-claim
           BINARY SEARCH.

You should be OK.

Rob

[former_member204618]

Rob,

Thanks for the reply, I had forgotten to add the active and claim fields.

Does this mean that it will find the very first record it finds or the first record in the array of matching keys ?

We are interested in finding the latest record to be changed which works just fine in a standard sequential read with the same sorted table but is extremely slow due to the sheer number of records being read. This is why we are hoping to use a Binary Search if possible.

Thanks

Craig

Message was edited by: Craig Armstead

[Former Member]

If you do F1 in READ, you'll find:

"The system reads the first entry in which the specified components k1 ... kn correspond with the values of v1 ... vn."

So, if you sort and read the way I have suggested, it should work - try it.

Rob

[Former Member]

I think it would be better to sort the table on active and claim fields. As per the binary search algorithm, it first divides the table into half and reads the key against the value and so on..i think example would be a better way to explain...lets say you have numbers 1..to ..100 in a table and you are searching for 34.

it would read the 50th record and if it is say 50.

next it would read the 25th record and if it is say 25.

It would carry to read the 38th record and so on.

Hence it is very critical to sort the table.

If we consider your case if the table is not sorted, there would be many records with same active and claim fields and whether it fetches the right result would depend on the data.

Regards

Anurag

[former_member204618]

Hi All,

Your responses have been great.

Here is a section of our code :-

DATA: lt_payi TYPE STANDARD TABLE OF iclpayi,

ls_payi TYPE iclpayi.

SORT lt_payi BY claim changetime DESCENDING.

READ TABLE lt_payi INTO ls_payi

WITH KEY claim = ls_bw_reserve-claim

BINARY SEARCH.

Are we all saying then that the above code will work just fine because we have sorted the table ASC by the KEY "claim" even if we are also sorting the table DESC for "changetime", since "changetime" is not part of the search KEY ?

We will test this obviously but we could do with knowing beforehand.

Thanks again for all your assistance.

Craig

[Former Member]

Yes - it will read the first record with the claim you have specified. Since you have also sorted by changetime (descending) that first record will be the one with the latest changetime.

(What happened to ACTIVE?)

Rob

[former_member204618]

Rob,

Thanks very much for your help. Once we have confirmed this works as expected I will reward accordingly.

Yeah ACTIVE was an error in the code and should be included and will when we change this.

Thanks again.

Craig

[former_member204618]

Rob,

Thanks very much, I can confirm that this does indeed work.

Sorting based on search key in asceding order with another descending field does produce the required result.

As in, picks the 1st record in the resultant search even when when there is more than 1 returned row matching the searched KEY field.

Exactly what we wanted, picking the latest changed record from a shadow table using BINARY SEARCH.

And again thanks to everyone for their input.

Cheers

Craig

[Former Member]

Search using read always pick the first record which matches the key.

[Former Member]

Check this link. its explaning how BINARY SEARCH Works.

Regards

Srikanth

[Former Member]

chk this

http://help.sap.com/saphelp_nw04/helpdata/en/fc/eb373d358411d1829f0000e829fbfe/content.htm

[Former Member]

Hi,

It will pick up the first record that matches the combination of active and claim...Which may not be the latest in the field changetime for the combination of active and claim..

For that try this..

SORT gt_icslaim_des BY active claim ASCENDING

changetime DESCENDING.

Thanks

Naren

[anversha_s]

hi craig,

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 (<b>from approximately 100 entries upwards</b>).

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.

rgds

anver

if hlped mark points