View previous topic :: View next topic
|
Author |
Message |
vijikesavan
Active User
Joined: 04 Oct 2006 Posts: 118 Location: NJ, USA
|
|
|
|
Hi Cobol experts,
My question is very basic question in binary search.
I have a table
Code: |
05 WS_TABLE occurs 0 to 100 depending on WS-MAX
ASCENDING KEY WS-KEY
INDEXED BY WS-INDEX
VALUE HIGH VALUES.
10 WS-KEY X(02).
10 WS-DATA X(10) |
My table is a variable length table. (Though the table is defined for max 100 I might have values only 20-25). Lets assume I have only 25 values.WS-MAX has 25.
While using SEARCH ALL, when does AT END condition happens, when it encounters 26th record or it goes till 100th record?
I am sorry for wasting your time on such silly questions, but I need this to be clarified.
Thanks |
|
Back to top |
|
|
Craq Giegerich
Senior Member
Joined: 19 May 2007 Posts: 1512 Location: Virginia, USA
|
|
|
|
AT END occurs when when SEARCH ALL does not find the value it is searching for. I would suggest you read the cobol manual. |
|
Back to top |
|
|
vijikesavan
Active User
Joined: 04 Oct 2006 Posts: 118 Location: NJ, USA
|
|
|
|
Thanks. I will read the manual for sure. Sometimes, you work on so many new features and forget the basics.
Thanks again. |
|
Back to top |
|
|
Bill O'Boyle
CICS Moderator
Joined: 14 Jan 2008 Posts: 2501 Location: Atlanta, Georgia, USA
|
|
|
|
IMHO, due to an absolute max of 100 entries, you'd be better off using either the SEARCH Verb or write your own In-Line PERFORM.
Generally, if the number of entries does not exceed 128, I use a sequential search.
Remember, to invoke a COBOL Binary Search, a CALL must be issued to a Run Time routine and therefore, you need to weigh this overhead against a sequential search, which would must likely (SEARCH verb) be resolved in-line (an In-Line PERFORM would undoubtedly be resolved in-line).
Just my .02 cents....
Bill |
|
Back to top |
|
|
dick scherrer
Moderator Emeritus
Joined: 23 Nov 2006 Posts: 19244 Location: Inside the Matrix
|
|
|
|
Hello,
Quote: |
While using SEARCH ALL, when does AT END condition happens, when it encounters 26th record or it goes till 100th record? |
Using your example, there are only 25 entries in the array. Items 26 - 100 would not "exist" and would not be "searched".
A couple of thoughts about performance improvements looking for a match in an array.
If the current value is the same as the value last searched, there should be no need to search. The required entry is already found (or not if it does not exist). Either way, no need to search again for the same "key".
When doing a sequential search, continuing from the current position is often very much faster than starting from the beginning when the new "key" is greater than the previous search key.
There is also a way to improve the search if the current key is less than the previous search key. Depending on how far the previous key is into the array, the search might be done by decrementing from the current positon or by starting over at the beginning and incrementing. |
|
Back to top |
|
|
Terry Heinze
JCL Moderator
Joined: 14 Jul 2008 Posts: 1249 Location: Richfield, MN, USA
|
|
|
|
Bill and Dick have made very good points. One thing to remember about one of Dick's comments "If the current value is the same as the value last searched, there should be no need to search. The required entry is already found." is that the required entry might have been a "not found" condition. I made that mistake once. When comparing the current search argument with the previous search argument, also keep track of the fact that the previous search might have resulted in the "at end" condition. |
|
Back to top |
|
|
dick scherrer
Moderator Emeritus
Joined: 23 Nov 2006 Posts: 19244 Location: Inside the Matrix
|
|
|
|
Hello,
My bad
I should have specifically mentioned that. Hopefully, the code already "marks" a not found and that would still be available as well.
(Earlier post enhanced)
Good catch, Terry and thanx for the follow-up
d |
|
Back to top |
|
|
Robert Sample
Global Moderator
Joined: 06 Jun 2008 Posts: 8697 Location: Dubuque, Iowa, USA
|
|
|
|
Quote: |
While using SEARCH ALL, when does AT END condition happens, when it encounters 26th record or it goes till 100th record? |
To me, this says vijikesavan does not understand binary search. With 100 elements in the table, binary search will not do more than 7 iterations, comparing no more than 9 or maybe 10 items. Talking about encountering a particular record, especially the records at the end of the table, just doesn't make sense. |
|
Back to top |
|
|
Terry Heinze
JCL Moderator
Joined: 14 Jul 2008 Posts: 1249 Location: Richfield, MN, USA
|
|
|
|
Yes, as Dick alluded to, the 1st element to be compared with the search argument will be the element midway between the beginning of the table and the end (occurrence 13? of a 25 element table). The 26th occurrence will never be compared to the search argument. The Language Reference and Programming Guide tell you everything you need to know and have examples, but they don't explain the mechanics of a binary search. The way a binary search works might be found by Google. |
|
Back to top |
|
|
vijikesavan
Active User
Joined: 04 Oct 2006 Posts: 118 Location: NJ, USA
|
|
|
|
Thanks everyone for all your valuable replies. Yes. I know binary search would not go to 26th search at all. Just to be sure..Its just one of my bad brain functioning days!.once again thanks everyone. |
|
Back to top |
|
|
|