MVSFORUMS.com

dharmaraju · Posted: Thu Mar 13, 2003 6:04 am Post subject: search all

Hi all,

When we search ,an array having spaces, using SEARCH ALL, the search fails. Can any one explain what happens in terms of memory during the SEARCH ALL

Rgds
Raj

DaveyC · Posted: Thu Mar 13, 2003 9:51 am Post subject:

Nothing happens to memory during SEARCH ALL. SEARCH ALL is a standard binary search, so you have to make sure all your array elements are in sorted order with no duplicates for it to be successful.
_________________
Dave Crayford

Glenn · Beginner Joined: 23 Mar 2003 Posts: 56 Topics: 3

When you load the array for a search all, it must be sorted.

If you do not completely load the array, fill the rest of the array with high-values. This should take care of things for you...

dharmaraju · Posted: Mon Mar 24, 2003 4:03 am Post subject:

HI..

I have tried that and worked fine. The intention of the question is just I want to know why binary search fails when there are spaces in the array. I tried by keeping only one data in an element.
_________________
Arigato Guzaimasu ( Thank you in Japanese)
Dharmaraj

Glenn · Beginner Joined: 23 Mar 2003 Posts: 56 Topics: 3

spaces are X'40' while alphabetics and numerics are X'Cx' through X'Fx' where x is a number.

Sorted means byte sorted...if spaces or X'40' appears last, this means the array is not sorted.

dharmaraju · Posted: Mon Mar 24, 2003 5:32 am Post subject:

Hi Glen,
I agree ur answer. Sorting is a solution whenever Search All fails. But I am not getting any idea why the Search All fails. I want to know the algorithm which Search All uses and why it fails whenever there are spaces in between. Coz it doesnt happen in Search.
_________________
Arigato Guzaimasu ( Thank you in Japanese)
Dharmaraj

Dibakar · Posted: Mon Mar 24, 2003 8:17 am Post subject:

Dharmaraju,

I haven't used search all but from my understanding of Binary Search I guess if you have an array containing '11,SPACES,13,14 ,15' and you are trying to search '11' then it fail because first it will look at middle (ie 3rd) element which is 13.

Since 11 < 13 so it will now look at middle of 1st and 3rd (ie 2nd) element.

Now since SPACES < 11 < 13 so next it will look for middle of 2nd and 3rd element.

Now since 11 is NOT positioned between SPACES and 13 so SEARCH ALL will not find 11, though it is there in the complete array.

But if you try to search for 14 then it will work.

Guess what will happen if you look for a 'COBOL' in a dictionary and you are not told that because of printing mistake it got listed among the words starting with 'K'!

Diba

Corrected (NOT was missing) and reformated.

Glenn · Beginner Joined: 23 Mar 2003 Posts: 56 Topics: 3

Dibakar gives an adequate description of SEARCH ALL. SEARCH ALL is a binary search, while SEARCH is a sequential search.

A sequential search starts at the beginning and looks at each and every item encountered in the array. It is not required therefore for this array to be sorted.

A binary search uses divide and conquer as described in Dibakar's description. Therefore it is an absolute requirement for the array to be sorted when SEARCH ALL is used, since it uses relative positions and comparisons to locate the item in the array.

To extend upon the previous description:

11, space, 13, 14, 15. Really the bytes are compared here so it's:

F1F1,4040,F1F2,F1F3,F1F4,F1F5. We search for 11.

1) Binary search finds the approximate center of the array... in this case it's 13.
2) Is 11 = 13? No. Is 11 > 13? No. Is 11 < 13 Yes. So we find the center of the array between our comparison and 13...
3) Center of the array is now space. Is 11 = space? No. Is 11 < space? No (since we're comparing F1F1 and 4040, 40 is less than F1). Is 11 > space? Yes. So we find the center of the array between space and 13...that's 12...
4) Center of the array is now 12... Is 11 = 12? No. Is 11 > 12? No, is 11 < 12? Yes. We find the center of the comparison and the array...this is an array of one item, so the search ends.
5) Result - 11 is not in the array. But guess what? it is...

Hopefully you see what is going on - the SEARCH ALL failed in this search. SEARCH ALL is only valid if the array is already sorted before it is called....

Hope this helps.

Dibakar · Posted: Tue Mar 25, 2003 1:55 am Post subject:

Thanks Glenn.

Isn't 'ALL' a bad choice of word here where 'BIN' or 'BINARY' would have been more appropriate.

Though I was aware of binary search from my college days I didn't knew that in COBOL its called 'SEARCH ALL'. So when somebody asked me for first time the diffrence between 'SEARCH' and 'SEARCH ALL' I said its same as between 'FIND' and 'FIND ALL' of ISPF Edit.

Since I appear in lot of interviews so I don't remember whether I passed or flunked that interview!

Diba.

dharmaraju · Posted: Tue Mar 25, 2003 7:58 am Post subject:

thatz fantastic ..................
One more thing is , the SEARCH ALL allows only EQUAL TO condition in the WHEN clause. Is it because of the same process which Glenn explained???
throw some light on it.............
_________________
Arigato Guzaimasu ( Thank you in Japanese)
Dharmaraj

Dibakar · Posted: Wed Mar 26, 2003 2:30 am Post subject:

Raj,

Binary search is generally assosciated to find if a given element exist or not but it could be easily used to find nearest match.

If you look at this algorith then you will notice that when no match is found then -

1 If x < a(j) then it is the nearest match (of greater value) to x.

2 If a(j) < x then it is the nearest match (of lesser value) to x.

3 x < a(j) and j > 1 then a(j-1) is the nearest match (of lesser value) to x.

I don't know why COBOL doesn't use it but I think CICS uses it when we try to read a record from a file with key value greater/lesser than something.

Diba

dharmaraju · Posted: Wed Mar 26, 2003 3:11 am Post subject:

any more answers?????????????
_________________
Arigato Guzaimasu ( Thank you in Japanese)
Dharmaraj

Glenn · Beginner Joined: 23 Mar 2003 Posts: 56 Topics: 3

I'm not sure what answer you are looking for. There's really not that much of a need to test. As illustrated though you can always leave the index and get the "next best thing", although I understand there's no index set in the SEARCH ALL if there's not a match.

If it helps for educational purposes:

This code: