|
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"<<endl;
return -1;
}
int offsetMid= (tail-start)/2/sizeof(int);
cout<<"offset: "<<offsetMid<<" mid " <<*(start+offsetMid)<<endl;
cout<<start<<" " <<tail<<endl;
if(target == *(start+offsetMid) ){
cout<<"mid"<<endl;
return (offsetMid+1);
}
if(*(start+offsetMid) > target){
cout<<"left"<<endl;
tail = start+(offsetMid-1)*sizeof(int);
return Search(target, start, tail);
}
if(*(start+offsetMid) < target){
cout<<"right"<<endl;
start = start+(offsetMid)*sizeof(int);
return Search(target,start , tail);
}
}
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 is
gcc version 6.2.1 20160916 (Red Hat 6.2.1-2) (GCC) Another weird thing
int offsetMid= (tail-start)/2/sizeof(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.
|
|
|
|
|
I'm so sorry about that. This is my first time come here, I'm not familiar with here.So I just want more people can see my problem. Thank you for you advice.
|
|
|
|
|
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.
modified 3-Feb-17 5:26am.
|
|
|
|
|
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" };
char* RodentAnimals[4] = { "Mouse", "Rat", "Rabbit", "Fox" };
char* WildAnimals[4] = { "Elephant", "Rhino", "Lion", "Tiger"};
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[^]
In vino veritas
modified 3-Feb-17 13:39pm.
|
|
|
|
|
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 would think your Search() function could be quite a bit simpler if it weren't using pointers for start and tail. 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
|
|
|
|
|
Yeh, I thought that pointor is convient, but now I know that they are also dangerous
|
|
|
|
|
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
|
|
|
|
|
I have two PCs with VS2008 installed. One PC belongs to me, the other is a loaner PC being used by remote access. If I create a simple smartdevice dialog application, my PC builds it fine. The other PC, when compiling stdafx.cpp spews the following (truncated to avoid insanity...). There are no seperate include dirs for headers, etc. I've compared project settings between PCs, etc. The only thing I found different is that the failing machine did not have the Windows 7 SDK installed.
Clearly I'm missing a header or a macro definition, but I don't see it. Ideas?
1>Compiling...
1>stdafx.cpp
1>c:\program files\windows ce tools\sdks\lync817_sdk\include\x86\stdlib.h(179) : error C2146: syntax error : missing ';' before identifier 'errno_t'
1>c:\program files\windows ce tools\sdks\lync817_sdk\include\x86\stdlib.h(179) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
1>c:\program files\windows ce tools\sdks\lync817_sdk\include\x86\stdlib.h(184) : error C2146: syntax error : missing ';' before identifier 'errno_t'
1>c:\program files\windows ce tools\sdks\lync817_sdk\include\x86\stdlib.h(184) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
1>c:\program files\windows ce tools\sdks\lync817_sdk\include\x86\stdlib.h(184) : error C2086: 'int __checkReturn_wat' : redefinition
1> c:\program files\windows ce tools\sdks\lync817_sdk\include\x86\stdlib.h(179) : see declaration of '__checkReturn_wat'
1>c:\program files\windows ce tools\sdks\lync817_sdk\include\x86\stdlib.h(196) : error C2146: syntax error : missing ';' before identifier 'errno_t'
1>c:\program files\windows ce tools\sdks\lync817_sdk\include\x86\stdlib.h(196) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
Charlie Gilley
<italic>Stuck in a dysfunctional matrix from which I must escape...
"Where liberty dwells, there is my country." B. Franklin, 1783
“They who can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety.” BF, 1759
|
|
|
|
|
Smells to me like the sick machine is missing (or just can't find) errno.h which is where errno_t is defined. Without the SDK there may be a whole bunch of low level include files missing.
Happy hunting!
Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
Sorry you being very silly for a programmer it isn't insanity it makes perfect sense
Look again at the error .. note the directories in particular
"c:\program files\windows ce tools\sdks\lync817_sdk\include\x86\stdlib.h"
There is nothing standard about and lets cover the basics
1.) The compiler is accessing files specific to some Windows CE SDK
2.) You are on a PC so you will need a SDK for Windows CE or the Compiler project settings are wrong
3.) The message is very clear what the problem is AKA it doesn't know what errno_t, it is an unknown type
4.) On a normal PC system errno_t is defined in the system file errno.h you use #include <errno.h>
5.) Being a system file the directories etc will be in the project settings as per note above.
Anyhow I am not a mind reader what you are doing but for some reason the compilation is using files in Windows CE SDK. Install the CE SDK if that is what you are doing or look at your project settings they are wrong. You could also just recreate the project from scratch on that machine it takes like 1 minute ... Create project from existing source is your friend.
In vino veritas
|
|
|
|
|
Leon - yes, yes, you are correct. It is for a CE, Windows Embedded Compact, a Smart Device, and let's see what does Microsoft call them now? Hmm IoT or something. Note:
Quote: If I create a simple smartdevice dialog application, my PC builds it fine
All of the defaults are set up by VS2008, so I admittedly was hoping for a "oh, yeah, I've seen that before" response. Nothing magic here, this is a completely default mfc dlg app that is the default framework of an application.
This is an argument between VS2008 and I think the SDK, and years ago, I solved this. Just having a senior moment.
Charlie Gilley
<italic>Stuck in a dysfunctional matrix from which I must escape...
"Where liberty dwells, there is my country." B. Franklin, 1783
“They who can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety.” BF, 1759
|
|
|
|
|
Hello,
Recently, we move from VisualStudio 2010 to 2013.
I use Ultimate Toolbox that I have compiled it with Visual C++ 2013 in a lib. It compiles and links without problem.
When I link this lib with my program, I get a link error: LNK2019 unresolved external symbol. With Visual C++ 2010, the link process was correct.
The symbol is the MonitorFromRect Windows function in COXToolTipCtrl:: CalculateInfoBoxRect().
We runs on Windows 7 Professionnal 64 bits. We compile on 32 bits Visual C++.
Is there a way to bypass this problem?
Thanks for any help.
Claude
|
|
|
|
|
Gagnon Claude wrote: Is there a way to bypass this problem?
Check your project settings to ensure the linker parameters are correct, and the library is included.
|
|
|
|
|
To elaborate on this suggestion, make sure that the linker uses the lib that you compiled with VS 2013, not the one that you compiled with VS 2010. The linker error may imply that it still sees the VS 2010 version. So, check the linker settings to see what search path it is using.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
|
|
|
|
|
I don't think you meant this message for me.
|
|
|
|
|
Hi Claude,
The reason of the problem is that the code uses the definition of MultiMon.h for function MonitorFromRect instead of using the native definition of this function coming from WinUser.h. Solution : remove line "include MultiMon.h" from OXToolTipCtrl.cpp to force the usage of WinUser.h definition for this function.
Florianne 
|
|
|
|
|
I open VS2015, click New Project, Select "Win32 Console Application"
Click OK.The dialog closes, then reopens.
Click OK.The dialog closes, then reopens.
Click OK.The dialog closes, then reopens.
.
.
.
C# apps work fine, just not C++,
Anyone seen this? Why can't I create a C++ console app?
If it's not broken, fix it until it is.
Everything makes sense in someone's mind.
Ya can't fix stupid.
|
|
|
|
|
What dialog do you mean? I don't have dialogs in my console apps and I've written a few hundred of them.
|
|
|
|
|
As I said, the New Project dialog
If it's not broken, fix it until it is.
Everything makes sense in someone's mind.
Ya can't fix stupid.
|
|
|
|
|
Visual Studio install has got corrupted somehow, go to Control panel on the Visual Studio entry do a repair. It usually fixes the problem.
In vino veritas
|
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
