Binary search

[Former Member]

What is the diff between linear search and binary search?

[Faaiez]

Hi Balu

The addition BINARY SEARCH 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.

The system searches for the relevant table types as follows:

· Standard tables

Linear search, where the runtime is in linear relation to the number of table entries.

· Sorted tables

Binary search, where the runtime is in logarithmic relation to the number of table entries.

· Hashed tables

The entry is found using the hash algorithm of the internal table. The runtime is independent of the number of table entries.

[Former Member]

Hi,

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.

[Former Member]

Hi Balu,

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 = <f> <result> BINARY SEARCH.

and

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.

Example

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.

Reward points if helpful.

Regards,

Hemant

[Former Member]

hi,

linear search searches one one records(sequentially from first record to last record.)it takes more time

Binary search applies binary logic..takes less time

gets the ( (first record + last record) / 2) = value..

Now search for the given record whether it is greater than or less than the VALUE above..

If it is greater, it considers the below records and apply the same logic as above for the below part..

If it is less, it considers the ABOVE records and apply the same logic as above for the above part..

You need to sort the tables for Binary searc, if not you will not get the proper output.

Anyways SAP does this logic No need to worry!!!.

Hope you understood,,

Rewards if useful

regards,

nazeer

Message was edited by:

nazeer shaik

[sreeramkumar_madisetty]

Hi

Have a look on the below link:

http://help.sap.com/saphelp_nw2004s/helpdata/en/fc/eb373d358411d1829f0000e829fbfe/frameset.htm

Regards,

Sreeram

[Former Member]

Hi,

In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a set of data for a particular value.

It operates by checking every element of a list one at a time in sequence until a match is found

A binary search (or binary chop) is a technique for finding a particular value in a sorted(ascending order) list. It makes progressively better guesses, and closes in on the sought value, by comparing an element halfway with what has been determined to be an element too low in the list and one too high in the list. A binary search finds the median element in a list, compares its value to the one you are searching for, and determines if it’s greater than, less than, or equal to the one you want. A guess that turns out to be too high becomes the new top of the list, and one too low the new bottom of the list. The binary search's next guess is halfway between the new list's top and bottom. Pursuing this strategy iteratively, it narrows the search by a factor 2 each time, and finds your value.

Rgds,

Prajith

[Former Member]

Please think of it like this :

Assume you have a pack of cards numbered 1 to 100 IN SORTED order.

Requirement : Find card numbered 12

LINEAR SEARCH : Look at each card in order, it will take 12 tries to achieve this.

BINARY SEARCH : Since the cards are sorted :

1. Cut the pack in half. You get card number 50. Since it is greater than 20, you discard the lower half from 50-100.

2. Now cut the remaining half into two - you get card number 25 . Since this is still greater than 20 discard the lower half again from 25-50.

3. Cut the pack in two again - this time card number 12 comes out , so you found it in three tries and hence it is faster.

This works only if the pack is sorted.

So if a table is sorted by a field F1, you can READ TABLE WITH KEY F1 = 12 BINARY SEARCH will be much faster.

Hope this helps

[Former Member]

hi balu,

linear search can search line by line from the database, where as binary search can seach the records by dividing total records by 2 ,

Ex: if ur itab has 10 records,

do u watn get 8 th record from that,

if it's binary search, then it divides total reocrds by 2 (i.e. 10/2 = 5) then it goes to second half because 8 th record is there in second half, then agian second half can divided by 2 then search that's how binary search works... where as linear search can search one by one...

regards..

seshu.