Searching for a particular address in a given range

This is a discussion on Searching for a particular address in a given range within the C Programming forums, part of the General Programming Boards category; Can anyone help me with searching for a particular address in a given range in C. like i have to ...

  1. #1
    Banned
    Join Date
    Jul 2011
    Posts
    12

    Searching for a particular address in a given range

    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.

  2. #2
    Registered User
    Join Date
    Aug 2010
    Location
    Rochester, NY
    Posts
    196
    Quote Originally Posted by Sjvlsdsd View Post
    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?

    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.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.
    Last edited by Adak; 07-30-2011 at 05:15 AM.

  4. #4
    Registered User
    Join Date
    Aug 2010
    Location
    Rochester, NY
    Posts
    196
    Quote Originally Posted by Adak View Post
    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.

    Yes, that is the difference between O(log(n)) (binary search) and O(n) (linear), haha.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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 >

  6. #6
    Registered User
    Join Date
    Aug 2010
    Location
    Rochester, NY
    Posts
    196
    lol, okay, we're thread jacking now, let's stop =).

  7. #7
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Sjvlsdsd View Post
    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.
    This is sufficiently vague that we're going to need to see some code to give you much help...

    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.
    Last edited by CommonTater; 07-30-2011 at 06:22 AM.

  8. #8
    Ultraviolence Connoisseur
    Join Date
    Mar 2004
    Posts
    472
    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...

  9. #9
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by nonpuz View Post
    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...

    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); }

  10. #10
    Registered User
    Join Date
    Jun 2005
    Posts
    6,205
    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.
    Right 98% of the time, and don't care about the other 3%.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Searching for a particular address in a given range
    By xyz1987 in forum C Programming
    Replies: 6
    Last Post: 11-20-2010, 07:24 AM
  2. Replies: 1
    Last Post: 11-07-2010, 10:39 PM
  3. IP address range matching
    By Thantos in forum Tech Board
    Replies: 2
    Last Post: 07-16-2009, 04:28 PM
  4. Block address from word address
    By xddxogm3 in forum Tech Board
    Replies: 0
    Last Post: 04-25-2007, 09:02 PM
  5. Range
    By volk in forum C Programming
    Replies: 3
    Last Post: 12-19-2002, 08:43 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21