cdc_sickle
asked on
Binary Search
How would i setup a binary search on an array with, oh, lets say 600 slots?
Binary search is pretty and the question gives me pause. I hesitate to give more info or actual "code" on this because of the outside chance some of the question askers are studens trying to get "too much" help.
If the array items are not already sorted I would use 'Quicksort' code to sort your array. There are several VB Quicksort Array source codes easily found and I believe even on this site..
The binary search I believe you want would be described as starting with the entire dataset of (600 items) as your "master group"
We determine if it has more than 2 items in the current group and if so then divide it in half to find a "center" item and compare to the center item of the group if your center item is BELOW < your SOUGHT item then the top half becomes the new master search tree group. If it is instead ABOVE > the other lower half is the new master group and the process repeats until your item matches the center dividing item or your current group contains less than three items in which case those remaining items are checked as "centers" were above and one is chosen and should hopefully match or else a "no match" condition is returned.
If the array items are not already sorted I would use 'Quicksort' code to sort your array. There are several VB Quicksort Array source codes easily found and I believe even on this site..
The binary search I believe you want would be described as starting with the entire dataset of (600 items) as your "master group"
We determine if it has more than 2 items in the current group and if so then divide it in half to find a "center" item and compare to the center item of the group if your center item is BELOW < your SOUGHT item then the top half becomes the new master search tree group. If it is instead ABOVE > the other lower half is the new master group and the process repeats until your item matches the center dividing item or your current group contains less than three items in which case those remaining items are checked as "centers" were above and one is chosen and should hopefully match or else a "no match" condition is returned.
make that "pretty simply"
ASKER
Well, i was doing the devide in half thing, but it got to the point where, what if the number is greater the 300.
600 \ 2 = 300
so then arrayfind > 300 so what would i do??
600 \ 2 = 300
so then arrayfind > 300 so what would i do??
Okay so for our example the records values just happen to equal their record numbers - so if your value is greater than 300 and you compare to item 300 then your remaining MASTER SET OF RECORDS your "Possibles" are the TOP 300 records 301 through 600. You then divide that 300 records which is more than two in half which is 150 records and compare to the record at 301+150 or "451" and say your searching for "376" so this time you are UNDER the center item so again you would now search the LOWER half of the split which is not 301 through 450 or only 150 records. Divide by two again and you get only 75 records so this time compare to record 301+75 or 376 and voila a match! Got it?
make that is NOW 301 through 450 or only 150 records
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Thanks. If you have any problems with your code not doing what you need post your code and I will help you debug it.
What type of data? Integer, String.
Define slots? Is that array elements?