Read table and binary search

[Former Member]

Hi all,

I have a simple query regarding read int_tab with binary search.

Why reading internal table with binary search fails if it is sorted in descending order table must be sorted in ascending order?

I check fo the algorithm of binary search, it does not talk about sort order. As far as my understanding goes binary search only require sorted table but while reading table in SAP it has to be sorted in ascending order!!

[Former Member]

Hello,

Binary search searches the given list by dividing it into two halves and searching the remaining half.

So, If the list is not sorted, the search would not be correct and it would not find the required value.

Hence, sorting should be done before giving binary search.

Thanks,

Sowmya Arni

[Former Member]

If you read my question properly, it says why sorting in ascending order is require and sorting in descending order will result in failour of read statement with binary search.

[Former Member]

Sorting in descending order also works for binary search.

In the read statement you need to use the same keys with which you are sorting the table.

[matt]

Why are you using binary search in the first place? Use a table of type SORTED.

matt

[Former Member]

@Sowmya: no descending sort will not work. See SAP documentation or write a test query and check

[Former Member]

First thing... Binary search never works with sorting by descending order.

now.. why it works with sorting with ASCENDING ORDER:

see.. how binary search works.

u always sort by that column of the table which u are passing as the KEY for reading. right!!!

when u specify binary search..It splits the table into two parts right in the middle.

then it checks what value u have searching for in the key.

if the search value is less than the value in the middle record, then it searches the upper part of the table. but if the value is greater than the middle record it searches in the lower part of the table.

but if the table is sorted in the DESCENDING order, then after splitting if the search value is less than the middle value it will search in the upper half of the table. But if wont find any thing .. as the lesser values will be in the lower half table. getting my point? same thing happens for a value which is greater than the middle value.

got my point?

thus reading with binary search ONLY WORKS WITH ASCENDING ORDER SORTING.

regards.

Somu

[Former Member]

Please be very careful what you write.

The BINARY SEARCH works always, even if the table is not sorted!

It never checks whether the table is sorted and in which order it is sorted.

It will onyl be successful if the table is sorted in ascending order.

And be aware, if the used key is unique, then the binary search will not stop at any record fulfilling the condition but at the smallest record:

A  a   1   
A  a   2
A  b   1
A  c  1
B  a  1
B  a  2

READ TABLE itab WITH key f1 = A f2 = a BINARY SEARCH.
 

will always give the first line not the second

You can start a loop and get all lines fulfilling the condition.

Siegfried

[Former Member]

>

> Please be very careful what you write.
> 
> The BINARY SEARCH works always, even if the table is not sorted!
> It never checks whether the table is sorted and in which order it is sorted.
> 

i think its wrong to say binary search works always and its no point using a binary search when its not sorted.

loop and get all lines fulfilling the condition.

check this

A b 1
A a 1
D a 1
B a 2
C a 3
B a 1
C a 4

read <itab> into <wa> with key f1 = D binary search.

since this is not sorted according to binary search algorithm it wont return a value

so its wrong to say that it works all the time even if its not sorted.

Nafran

[Former Member]

this has nothing to do with SAP its how the binary search works. what ever the language you use binary search will only work for ascending soft only.

check on how binary search works

Nafran

[matt]

>

> this has nothing to do with SAP its how the binary search works. what ever the language you use binary search will only work for ascending soft only.
> 
> check on how binary search works
> 
> Nafran

What's critical is that the table is ordered in such a way that the comparator will always say that the next element is greater or equal to the current element (up to the element before last). So, you can write a binary search that works for descending sort, by using a comparator of "<" instead of ">"... pedantic, I know...

[Former Member]

> since this is not sorted according to binary search algorithm it wont return a value

so what, it does not find a value and what does this tell you ... nothing, because you don't know whether

it must return a value, maybe there is not record or this key.

I works means, that it do not give you an error, it does not dump. It even returns values, but not all values. Not sorted can mean, that nearly all values are sorted, besides one. That means if can find a

lot of values but not all.

I said you must be careful.

And the property that it returns the very first of group with same keys is not related to the binary search.

Binary search is also done on the database there this property does not hold.

Siegfried

[Former Member]

Problem not solved exactly,but at last i got lot more information from the last few replies

[Former Member]

> Problem not solved exactly

I have no idea what you would take as exactly solved.

It is possible to define a binary search which would work correctly in descending order, but then it would not work in ascending order

And a table which is sorted in the first half but not in the second, should work correctly for all records which are in the first half, they are all found! They binary searh never touches the second, so the second half can not have any influence.

Sorted tables are only sorted in ascending order, otherwise the binary search would not work

Siegfried