Can anyone help me with searching for a particular address in a given range in C. like i have to search for *ptr in range specified by *high and *low. i think it is not same as linear search. can someone provide some input. thanks.
Printable View
Can anyone help me with searching for a particular address in a given range in C. like i have to search for *ptr in range specified by *high and *low. i think it is not same as linear search. can someone provide some input. thanks.
If I am understanding your question correctly, if you are given a high address, and a low address, and no other information, you must perform a linear search...but since memory is random access, if you know the particular address you're searching for, why not just grab it?Quote:
Originally Posted by Sjvlsdsd
If you're looking for DATA, and getting the address of it, and you don't have any information about the block denoted by your high/low pointers, I'm pretty sure you have to do a linear search. Hope that helps...hope I'm understanding your question correctly.
Can you give an example, so we're clear exactly what you're doing? Also, how many addresses do you have to look through, in each search?
Lastly, how many times do you have to do this search for a target address? 1? 10,000?
Somewhere around 100 addresses, it will be faster to sort the addresses with a good sorter, and then use a binary search to find out if the target address is in the list.
If you have thousands of addresses, and you have to do this search hundreds of times, the improvement can be quite stunning if you use a good sorter.
I wrote up a program using this recently, for someone who's own program was too slow searching for words and all their permutations. His program did about one search, in 6 seconds. My program did a thousand searches, through the same names, in less than two tenths of a second.
A better algorithm (and fast sorting and searching), can make a HUGE difference. If you're looking for a speed increase, you've probably come to the right place. :)
Haha, awesome.Quote:
Originally Posted by Adak
Yes, that is the difference between O(log(n)) (binary search) and O(n) (linear), haha.
It was better than that! He had to search for not just the word that was given, but also test whether any permutation of the given word, was in the list of 1376 words. So he generated EVERY single permutation of the word, and THEN did a sequential search, for every single permutation. < OMG! >
I skipped all that by sorting the wordlist once, and then sorting the target word as well. Now just ONE binary search will find if any permutation of the word, is in the list or not. (Only one permutation of the word had to be found).
It was a thing of beauty, imo. So naturally nobody commented on it in that board. < LOL >
lol, okay, we're thread jacking now, let's stop =).
This is sufficiently vague that we're going to need to see some code to give you much help...Quote:
Originally Posted by Sjvlsdsd
In modern computers a programmer typically doesn't know --or care-- where his pointers point... we allow the system to assign them and for the most part don't actually care where the data is stored so long as we can get at it when we need it.
If *low and *high point to the same memory block, (ie you char * p = malloc(100); and assign points to this same object) then the memory is in fact in order and linear...so you can already do a binary search on it because the address ARE sorted.
Though as early pointed out if you know the address, you would just access it directly; therefore perhaps hes meaning how do I find the letter pointed to by *somep within the range low, high, which are boundaries pointing into a string?? In which case we just suggest strchr() or a for loop...
But all this also begs the question of why do we need to search if we already know the address...Quote:
Originally Posted by nonpuz
Perhaps our vague friend wants to know if a given pointer is between two other pointers (i.e. in a given range) in which case a simple if() statement will suffice...
Code:int InRange(char *ptr, char *start, char *end)
{ return (ptr >= start) && (ptr <= end); }
Given that the OP has another thread asking how to access all memory on a system, independently of OS, it's likely the wish is to search in a range of memory for some particular content.