Thr problem of the recursive algorithm to do binary search in a sorted array
-
I want to inplement a binary search algorithm of an order array.
int Array::Search(int target, int* start, int* tail){
if(start>tail){
cout<<"not find"< target){
cout<<"left"<
But it doesn't work, I know the parameter of the func should better be the index of the array rather than a pointor, I just want to try this way. The compiler I used isgcc version 6.2.1 20160916 (Red Hat 6.2.1-2) (GCC)
Another weird thing
int offsetMid= (tail-start)/2/sizeof(int);//by unit of int
Both tail and start are the type of int*, but the difference of them is counted by byte, so I must divide it by sizeof(int) to get the offset value.
if(*(start+offsetMid) > target)
But when I want to plus the offset value to the start address to get the value in a particular position, I shouldn't time it by sizeof(int).WHY??
-
I want to inplement a binary search algorithm of an order array.
int Array::Search(int target, int* start, int* tail){
if(start>tail){
cout<<"not find"< target){
cout<<"left"<
But it doesn't work, I know the parameter of the func should better be the index of the array rather than a pointor, I just want to try this way. The compiler I used isgcc version 6.2.1 20160916 (Red Hat 6.2.1-2) (GCC)
Another weird thing
int offsetMid= (tail-start)/2/sizeof(int);//by unit of int
Both tail and start are the type of int*, but the difference of them is counted by byte, so I must divide it by sizeof(int) to get the offset value.
if(*(start+offsetMid) > target)
But when I want to plus the offset value to the start address to get the value in a particular position, I shouldn't time it by sizeof(int).WHY??
You have already asked this question in QA. Please do not repeat questions in multiple places. Choose your forum, and stick with it.
Cheers, Mick ------------------------------------------------ It doesn't matter how often or hard you fall on your arse, eventually you'll roll over and land on your feet.
-
You have already asked this question in QA. Please do not repeat questions in multiple places. Choose your forum, and stick with it.
Cheers, Mick ------------------------------------------------ It doesn't matter how often or hard you fall on your arse, eventually you'll roll over and land on your feet.
-
I want to inplement a binary search algorithm of an order array.
int Array::Search(int target, int* start, int* tail){
if(start>tail){
cout<<"not find"< target){
cout<<"left"<
But it doesn't work, I know the parameter of the func should better be the index of the array rather than a pointor, I just want to try this way. The compiler I used isgcc version 6.2.1 20160916 (Red Hat 6.2.1-2) (GCC)
Another weird thing
int offsetMid= (tail-start)/2/sizeof(int);//by unit of int
Both tail and start are the type of int*, but the difference of them is counted by byte, so I must divide it by sizeof(int) to get the offset value.
if(*(start+offsetMid) > target)
But when I want to plus the offset value to the start address to get the value in a particular position, I shouldn't time it by sizeof(int).WHY??
Ok I want you to get out pen an paper and do this on a piece of paper You have have two integers in an array and the pointer to the first one we will call zero. So the second pointer must be exactly one integer away so it will be sizeof(integer) from the first pointer. Can you get what the result of this is (tail-start)/2 .. I will give you a hint if an integer is 2 bytes the answer is 1 byte. It doesn't matter what divisions you do after that you have lost alignment to the array your result can be some point in the middle of an integer. Nothing in all the code above deals with that problem and it's really simple to fix all you need is to add a simple +1 in exactly the right place. Start by fixing the alignment problem and most of the rest will drop out which was sort of the second you cottoned onto what is the middle of the array and what does that actually mean. Take a one integer array what is the middle mean, your code has to know what to do with pathological case. The two integer array is an edge case on dealing with even number arrays where the middle of the array isn't aligned to an integer pointer. This whole concept is sometimes called the post and fence problem, where you always need one more post than the gaps you span if you need to search.
-
I want to inplement a binary search algorithm of an order array.
int Array::Search(int target, int* start, int* tail){
if(start>tail){
cout<<"not find"< target){
cout<<"left"<
But it doesn't work, I know the parameter of the func should better be the index of the array rather than a pointor, I just want to try this way. The compiler I used isgcc version 6.2.1 20160916 (Red Hat 6.2.1-2) (GCC)
Another weird thing
int offsetMid= (tail-start)/2/sizeof(int);//by unit of int
Both tail and start are the type of int*, but the difference of them is counted by byte, so I must divide it by sizeof(int) to get the offset value.
if(*(start+offsetMid) > target)
But when I want to plus the offset value to the start address to get the value in a particular position, I shouldn't time it by sizeof(int).WHY??
I would think your
Search()function could be quite a bit simpler if it weren't using pointers forstartandtail. Being pointers, as opposed to actual values, does not seem to serve a purpose here."One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
-
You have already asked this question in QA. Please do not repeat questions in multiple places. Choose your forum, and stick with it.
Cheers, Mick ------------------------------------------------ It doesn't matter how often or hard you fall on your arse, eventually you'll roll over and land on your feet.
U are totally right, I found I made a silly mistake in Creator function that I DID'T post it up . Thank u for your answer and your patient, I hope my moron question didn't make you confused, if it is, I'm so sorry about that and the time u waste on my question.
-
Ok I want you to get out pen an paper and do this on a piece of paper You have have two integers in an array and the pointer to the first one we will call zero. So the second pointer must be exactly one integer away so it will be sizeof(integer) from the first pointer. Can you get what the result of this is (tail-start)/2 .. I will give you a hint if an integer is 2 bytes the answer is 1 byte. It doesn't matter what divisions you do after that you have lost alignment to the array your result can be some point in the middle of an integer. Nothing in all the code above deals with that problem and it's really simple to fix all you need is to add a simple +1 in exactly the right place. Start by fixing the alignment problem and most of the rest will drop out which was sort of the second you cottoned onto what is the middle of the array and what does that actually mean. Take a one integer array what is the middle mean, your code has to know what to do with pathological case. The two integer array is an edge case on dealing with even number arrays where the middle of the array isn't aligned to an integer pointer. This whole concept is sometimes called the post and fence problem, where you always need one more post than the gaps you span if you need to search.
-
I would think your
Search()function could be quite a bit simpler if it weren't using pointers forstartandtail. Being pointers, as opposed to actual values, does not seem to serve a purpose here."One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
-
thank u for your answer and your patient. You are so nice! It really teach me a lot, I get more than I thought. Thank u!
No worries can I also give you a much safer option which I always try to teach to new graduates Don't move the entries at all in the sort. Make yourself an array of pointers to the entries and shuffle your pointers in your private array. The reasons are obvious 1.) The is no risk of damaging the original data and if you want to undo the function it's instant 2.) On most systems these day an integer is 32bits as is a pointer so it is the same speed to sort them. 3.) For complex types doubles, floats, strings the pointer is a lot smaller than the data. 4.) The source data doesn't have to be in the same place, it can be spread out all over the place the pointers don't care A common test I set for new employees look like this .. Please write a routine to sort these animals
char* DomesticAnimals[4] = { "Cat", "Dog", "Goat", "Cow" }; // Some domestic animals .. feel free to add some
char* RodentAnimals[4] = { "Mouse", "Rat", "Rabbit", "Fox" }; // Some rodent animals .. feel free to add some
char* WildAnimals[4] = { "Elephant", "Rhino", "Lion", "Tiger"}; // Some wild animals .. feel free to add some,Basically you copy or move the entries you don't get the job. The three different source arrays throws most graduates for a loop they feel they have to move something. Even if they go for an "in place" sort they put wrong animals in wrong categories and they foul my database. You don't move anything, you make you own private array of char* pointers and point alternate strings and sort whats pointed to with a routine. There are 12 entries above so all you need is
char* myArray[12];
Load each entry to a pointer in that array and sort, and you don't move anything and you don't risk my data if you botch it. This example above sort of makes it very clear why you don't ever move the data .. not ever! If you want to see the trick of sorting pointers large scale open a windows folder viewer .. what do you think they are doing they don't ever really move or copy the data in anyway it's too risky and slow. It sorts out those who can program from those who can just write code very quickly. I would expect a good programmer to be able to write a bubble or quick sort on that array in about 20 lines of code. Here is the standard Rossetta code for it which is 15 lines Sorting algorithms/Quicksort - Rosetta Code[
-
No worries can I also give you a much safer option which I always try to teach to new graduates Don't move the entries at all in the sort. Make yourself an array of pointers to the entries and shuffle your pointers in your private array. The reasons are obvious 1.) The is no risk of damaging the original data and if you want to undo the function it's instant 2.) On most systems these day an integer is 32bits as is a pointer so it is the same speed to sort them. 3.) For complex types doubles, floats, strings the pointer is a lot smaller than the data. 4.) The source data doesn't have to be in the same place, it can be spread out all over the place the pointers don't care A common test I set for new employees look like this .. Please write a routine to sort these animals
char* DomesticAnimals[4] = { "Cat", "Dog", "Goat", "Cow" }; // Some domestic animals .. feel free to add some
char* RodentAnimals[4] = { "Mouse", "Rat", "Rabbit", "Fox" }; // Some rodent animals .. feel free to add some
char* WildAnimals[4] = { "Elephant", "Rhino", "Lion", "Tiger"}; // Some wild animals .. feel free to add some,Basically you copy or move the entries you don't get the job. The three different source arrays throws most graduates for a loop they feel they have to move something. Even if they go for an "in place" sort they put wrong animals in wrong categories and they foul my database. You don't move anything, you make you own private array of char* pointers and point alternate strings and sort whats pointed to with a routine. There are 12 entries above so all you need is
char* myArray[12];
Load each entry to a pointer in that array and sort, and you don't move anything and you don't risk my data if you botch it. This example above sort of makes it very clear why you don't ever move the data .. not ever! If you want to see the trick of sorting pointers large scale open a windows folder viewer .. what do you think they are doing they don't ever really move or copy the data in anyway it's too risky and slow. It sorts out those who can program from those who can just write code very quickly. I would expect a good programmer to be able to write a bubble or quick sort on that array in about 20 lines of code. Here is the standard Rossetta code for it which is 15 lines Sorting algorithms/Quicksort - Rosetta Code[
Thank u for sharing me this valuable experience, I will pay more attention when doing that. Never change the original data when sorting, just creat a new array that consist of the addresses of the elements in the original array, then change the order of the address in the new array.And the illustration of the windows folder viewer is quite interesting.
-
I want to inplement a binary search algorithm of an order array.
int Array::Search(int target, int* start, int* tail){
if(start>tail){
cout<<"not find"< target){
cout<<"left"<
But it doesn't work, I know the parameter of the func should better be the index of the array rather than a pointor, I just want to try this way. The compiler I used isgcc version 6.2.1 20160916 (Red Hat 6.2.1-2) (GCC)
Another weird thing
int offsetMid= (tail-start)/2/sizeof(int);//by unit of int
Both tail and start are the type of int*, but the difference of them is counted by byte, so I must divide it by sizeof(int) to get the offset value.
if(*(start+offsetMid) > target)
But when I want to plus the offset value to the start address to get the value in a particular position, I shouldn't time it by sizeof(int).WHY??
Your code do not behave the way you expect, and you don't understand why ! There is an almost universal solution: Run your code on debugger step by step, inspect variables. The debugger is here to show you what your code is doing and your task is to compare with what it should do. There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug. Debugger - Wikipedia, the free encyclopedia[^] Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^] The downside of this solution: - It is a DIY, you are the one tracking the problem and finding its roots, which lead to the solution. The upside of this solution: - You see your code behavior, you match it against your expectations. secondary effects - Your will be proud of finding bugs yourself. - Your skills will improve. You should find pretty quickly what is wrong.
Patrice “Everything should be made as simple as possible, but no simpler.” Albert Einstein