| View previous topic :: View next topic |
| Author |
Message |
pzmohanty
Beginner
Joined: 20 May 2004
Posts: 97
Topics: 43
Location: hyderabad, India
|
 Posted: Tue Aug 15, 2006 6:57 am Post subject: how to search all the existence of data using BINARY SEARCH |
 |
|
Hi All,
We all know that we can search for all the occurence of a condition in a table using LINEAR search by using following code :-
| Code: | MOVE 'N' TO END-OF-TABL.
SET WS-IDX TO 1.
PERFORM UNTIL END-OF-TABL = 'Y'
SEARCH WS-TABL AT END MOVE 'Y' TO END-OF-TABL
WHEN NAME(WS-IDX) = 'XYZ'
DISPLAY COST(WS-IDX)
SET WS-IDX UP BY 1
END-SEARCH
END-PERFORM. |
The above cobol code is for linear SEARCH , using which I can display cost of all the entry in the table where name is 'XYZ'
My question is can the same objective be achieved using BINARY SEARCH.
If yes ,let me know how I can do that , considering the fact that BINARY SEARCH has its own logic ( Divide & Rule ) for searching.
_________________
Priya Ranjan Mohanty
Consultant
Kanbay Software (I) pvt. Ltd.
Hyderabad |
|
| Back to top |
|
 |
shekar123
Advanced
Joined: 22 Jul 2005
Posts: 528
Topics: 90
Location: Bangalore India
|
|
| Back to top |
|
|
ofer71
Intermediate
Joined: 12 Feb 2003
Posts: 358
Topics: 4
Location: Israel
|
| Posted: Tue Aug 15, 2006 7:17 am Post subject: |
|
|
I have two REXX examples: Iterative and recursive.
The iterative example:
| Code: | /****************************** REXX ******************************** */
/* */
/* Name.......: BINISRCH */
/* */
/* Function...: Iterative binary search. */
/* */
/* Date.......: 13/12/2004. */
/* */
/* Author.....: OFER */
/* */
/* Reqirements: - */
/* */
/* Description: Search a sorted array by repeatedly dividing the */
/* search interval in half. */
/* Complexity: 0(log n). */
/* */
/* INPUT: Supply your array in DATA. */
/* Make sure that DATA.0 contains the number of */
/* elements in the array (filled automatically by */
/* EXECIO). */
/* */
/**********************************************************************/
ADDRESS TSO "ALLOC FI(SAMPDATA) DA('your.input.dataset') SHR"
"EXECIO * DISKR SAMPDATA (STEM DATA. FINIS"
"FREE FI(SAMPDATA)"
SAY BIN_SEARCH('your_target')
RETURN
/*------------------------------------------------------------------*/
BIN_SEARCH:
/*------------------------------------------------------------------*/
ARG TARGET
TOP = DATA.0
BOT = 1
FOUND = 0
DO WHILE (FOUND = 0 & TOP >= BOT)
MID = (TOP + BOT) % 2
IF TARGET = DATA.MID THEN
FOUND = 1
ELSE
IF TARGET < DATA.MID THEN
TOP = MID - 1
ELSE
BOT = MID + 1
END
RETURN MID
|
The recursive example:
| Code: | /****************************** REXX ******************************** */
/* */
/* Name.......: BINRSRCH */
/* */
/* Function...: Recursive binary search. */
/* */
/* Date.......: 13/12/2004. */
/* */
/* Author.....: OFER */
/* */
/* Reqirements: - */
/* */
/* Description: Search a sorted array by repeatedly dividing the */
/* search interval in half. */
/* Complexity: 0(log n). */
/* */
/* INPUT: Supply your array in DATA, the number of */
/* elements in the array in TOP, and the target */
/* key in TARGET. */
/* */
/**********************************************************************/
ADDRESS TSO "ALLOC FI(SAMPDATA) DA('your.input.dataset') SHR"
"EXECIO * DISKR SAMPDATA (STEM DATA. FINIS"
"FREE FI(SAMPDATA)"
TARGET = 'ZZCU0019'
TOP = DATA.0
SAY BIN_SEARCH(1,TOP)
RETURN
/*------------------------------------------------------------------*/
BIN_SEARCH:
/*------------------------------------------------------------------*/
BOT = ARG(1)
TOP = ARG(2)
IF TOP < BOT THEN
RETURN 0
MID = (TOP + BOT) % 2
IF TARGET = DATA.MID THEN
RETURN MID
ELSE
IF TARGET < DATA.MID THEN
X = BIN_SEARCH(BOT,MID-1)
ELSE
X = BIN_SEARCH(MID+1,TOP)
RETURN MID
|
You can find some omportant information about binary search here.
O.
________
vapor genie vaporizer
Last edited by ofer71 on Sat Feb 05, 2011 11:40 am; edited 1 time in total |
|
| Back to top |
|
|
pzmohanty
Beginner
Joined: 20 May 2004
Posts: 97
Topics: 43
Location: hyderabad, India
|
| Posted: Tue Aug 15, 2006 7:41 am Post subject: |
|
|
Hi ofer71,
thanks for the early reply.....
But my original question is still unanswered.....
Can we find all the occurences of a data in the table using BInary Search..
_________________
Priya Ranjan Mohanty
Consultant
Kanbay Software (I) pvt. Ltd.
Hyderabad |
|
| Back to top |
|
|
pzmohanty
Beginner
Joined: 20 May 2004
Posts: 97
Topics: 43
Location: hyderabad, India
|
| Posted: Tue Aug 15, 2006 7:42 am Post subject: |
|
|
Hi all,
When I am saying BINARY SEARCH...I am talking about BINARY SEARCH facility of COBOL ( SEARCH ALL ).
_________________
Priya Ranjan Mohanty
Consultant
Kanbay Software (I) pvt. Ltd.
Hyderabad |
|
| Back to top |
|
|
shekar123
Advanced
Joined: 22 Jul 2005
Posts: 528
Topics: 90
Location: Bangalore India
|
|
| Back to top |
|
|
kolusu
Site Admin
Joined: 26 Nov 2002
Posts: 12375
Topics: 75
Location: San Jose
|
| Posted: Tue Aug 15, 2006 7:52 am Post subject: |
|
|
| pzmohanty wrote: | Hi ofer71,
thanks for the early reply.....
But my original question is still unanswered.....
Can we find all the occurences of a data in the table using BInary Search.. |
You mean when your internal table has duplicates for the search key ?
_________________
Kolusu
www.linkedin.com/in/kolusu |
|
| Back to top |
|
|
pzmohanty
Beginner
Joined: 20 May 2004
Posts: 97
Topics: 43
Location: hyderabad, India
|
| Posted: Tue Aug 15, 2006 7:59 am Post subject: |
|
|
Hi Kolusu,
Yes , my question is if my table data has duplicate entries , then is it possible to find all the entries satisfying the condition using BINARY SEARCH of cobol.
_________________
Priya Ranjan Mohanty
Consultant
Kanbay Software (I) pvt. Ltd.
Hyderabad |
|
| Back to top |
|
|
shekar123
Advanced
Joined: 22 Jul 2005
Posts: 528
Topics: 90
Location: Bangalore India
|
| Posted: Tue Aug 15, 2006 8:06 am Post subject: |
|
|
pzmohanty,
You cannot have duplicates in the keys .
| Quote: | To use the SEARCH ALL statement, your table must already be ordered on the key or keys coded in the OCCURS clause. You can use any key in the WHEN condition, but you must test all preceding data-names in the KEY option, if any. The test must be an equal-to condition, and the KEY data-name must be either the subject of the condition or the name of a conditional variable with which the tested condition-name is associated. The WHEN condition can also be a compound condition, formed from simple conditions with AND as the only logical connective. The key and its object of comparison must be compatible.
|
_________________
Shekar
Grow Technically |
|
| Back to top |
|
|
kolusu
Site Admin
Joined: 26 Nov 2002
Posts: 12375
Topics: 75
Location: San Jose
|
| Posted: Tue Aug 15, 2006 8:36 am Post subject: |
|
|
| Quote: |
Yes , my question is if my table data has duplicate entries , then is it possible to find all the entries satisfying the condition using BINARY SEARCH of cobol.
|
it will find the first key depending on the algorithm. Once key is found you need to search manually up and down for all other duplicates.
| Quote: |
You cannot have duplicates in the keys .
|
shekar123,
Not exactly true. You can have duplicates in the keys. The *only* requirement of SEARCH ALL(binary search) is that the data is sorted. If you have duplicate data, it will locate the first key item encountered by the logic The particular ordered key item you arrive upon is unpredictable.
Kolusu
_________________
Kolusu
www.linkedin.com/in/kolusu |
|
| Back to top |
|
|
pzmohanty
Beginner
Joined: 20 May 2004
Posts: 97
Topics: 43
Location: hyderabad, India
|
| Posted: Tue Aug 15, 2006 10:25 am Post subject: |
|
|
hi Kolusu,
| Quote: |
it will find the first key depending on the algorithm. Once key is found you need to search manually up and down for all other duplicates.
|
but as we know the table automatically gets sorted dependiing on the definition of table when search is performed.
i.e if table defn is :-
| Code: | 05 ws-tabl occurs 10 times ascending key is ws-num indexed by ws-idx.
10 ws-num pic 9(1). |
So when data is entered into the elements of the table ,they don't get sorted but they get sorted for the purpose of BINARY SERACH only when BINARY SEARCH is perfromed on them. ( plz correct if I am wrong ).
Now lets say data in the table is :
ws-num(1) = 5
ws-num(2) = 3
ws-num(3) = 1
ws-num(4) = 5
ws-num(5) = 3
ws-num(6) = 5
ws-num(7) = 3
And lets say BINARY SEARCH is following :
| Code: | SEARCH ALL WS-TABL AT END CONTINUE
WHEN WS-NUM = 3
CONTINUE
END-SEARCH. |
lets assume that the above BINARY SEARCH fetched me 3 from 5th element i.e WS-NUM(5) and value of WS-IDX index is 5 , then incrementing or decrementing the INDEX using SET may not fetch me all the other 3 in the table as they are actually not contigous in table.
Please help me to understand this.
_________________
Priya Ranjan Mohanty
Consultant
Kanbay Software (I) pvt. Ltd.
Hyderabad |
|
| Back to top |
|
|
kolusu
Site Admin
Joined: 26 Nov 2002
Posts: 12375
Topics: 75
Location: San Jose
|
| Posted: Tue Aug 15, 2006 10:35 am Post subject: |
|
|
pzmohanty,
| Quote: |
but as we know the table automatically gets sorted dependiing on the definition of table when search is performed.
|
Says who ? It is your duty to load the table in the sorted order. The table definition does not gurantee that your table is sorted no matter what sequence you load the table.
ex: run the below code and see the sysout.
| Code: |
01 TABLE-1.
05 WS-TABL OCCURS 10 TIMES
ASCENDING KEY IS WS-NUM
INDEXED BY WS-IDX.
10 WS-NUM PIC 9(2).
PROCEDURE DIVISION.
MOVE 1 TO WS-TABL(01)
MOVE 3 TO WS-TABL(02)
MOVE 4 TO WS-TABL(03)
MOVE 5 TO WS-TABL(04)
MOVE 6 TO WS-TABL(05)
MOVE 10 TO WS-TABL(06)
MOVE 2 TO WS-TABL(07)
MOVE 7 TO WS-TABL(08)
MOVE 9 TO WS-TABL(09)
MOVE 8 TO WS-TABL(10)
DISPLAY TABLE-1
|
| Quote: |
So when data is entered into the elements of the table ,they don't get sorted but they get sorted for the purpose of BINARY SERACH only when BINARY SEARCH is perfromed on them. ( plz correct if I am wrong ).
|
SEARCH ALL does not sort the table. It is the programmer's responsibility to have the data sorted so that search function works correctly.
You need to load the internal table in sorted order.
Hope this helps...
Cheers
Kolusu
_________________
Kolusu
www.linkedin.com/in/kolusu |
|
| Back to top |
|
|
|
|
|
FAQ
Search
Quick Manuals
Register
Profile
Log in to check your private messages
Log in
