Using the MATCH Function for a Linear Search and a Binary Search

Given the problem I have with images and blog posts, I’m trying something new. I uploaded the content of the post to my website and am using an iframe to post it here. Yes, the UI experience is somewhat different than scrolling the entire browser window but hopefully it is something most people will be OK with. And, yes, I can adjust both the height and the width of the iframe.

This approach has another benefit in that one can read the entire post on the home page itself.

Posted in Uncategorized

17 thoughts on “Using the MATCH Function for a Linear Search and a Binary Search

  1. Great post. The downside to using an iFrame of course is that it doesn’t publish in the RSS.

  2. Well you may see this as a benefit, in that it forces readers to go to the actual web page, but one issue with this is that your feed, at least as seen on Google Reader, doesn’t have any of the content displayed!
    Mathias

  3. So automatic translation from whatever markup format you’re comfortable using to the markup format required by this blog is just impossible?!

    I have a similar recurring issue: finding the first (topmost or leftmost) match in a sorted list with possibly many duplicate values. That’s easily dealt with for numbers using

    C2: =MATCH(if(C1>=0,0.999999999999998,1.00000000000002)*C1,list)+1
    C3: =IF(C1=INDEX(list,C2),C2,#N/A)

    but it requires more work for strings

    C2: =MATCH(C1,list)
    C3: =MATCH(LEFT(C1,LEN(C1)-1),list)
    C4: =MATCH(C1,INDEX(list,C3):INDEX(list,C2),0)

    Anyway, hasn’t this been discussed many times already in Excel newsgroups?

  4. I think Mathias is saying he has to come visit this site rather than just read the post in his feed reader. I don’t subscribe to feeds that don’t put the full post in the feed unless it’s really worth it. Methods in Excel is an example of an exception. Tushar’s posts on DDoE would also be an exception, but I’m biased. Anyway, posts from me will still be viewable in the RSS.

  5. I don’t like blogs that don’t put the whole post into their feeds. I still follow some, but I am not as likely to read the whole post unless the small taste that’s published is very interesting.

  6. Tushar,
    I’ve been using exact match to determine of a value exists in another data set (=NOT(ISERROR(MATCH(SearchValue,SearchData,0)))

    Based on your article, I should use another method. I don’t think I should use the Binary seach since SearchData is not sorted which would give unreliable results. My next best idea is =(COUNTIF(SearchData,SearchValue)>0). Is COUNTIF any faster than the LINEAR unsorted Search?

  7. Alex: If the performance of your Excel model is acceptable, I wouldn’t change anything. As far as COUNTIF goes, I suspect it is slower than MATCH in linear mode since it must check every value whereas MATCH can quit as soon as it finds one match. But, you may want to verify the results for yourself.

  8. Tushar: Thanks. It appears that COUNTIF is no faster. I wonder if a UDF might perform better.

  9. Its possible to make a linear search UDF that is faster at recalculating on unsorted data, by storing the row number that was found in the first calculation and then checking the result for that row number on subsequent recalculations.

    This algorithm is only faster if the data to be found exists in the same place as it was at the last calculation.
    So for example if you add a row at the top of the data it won’t be any faster, but if you change a single value in 10K rows of data it will mostly be a LOT faster.

    for most spreadsheets this works well in practice.

  10. Jimmy –

    It’s a balancing act between protecting your stuff (from scrapers) and sharing your stuff (with readers). I err on the side of the readers, and once in a while track down the scumbags that repost my stuff.

  11. Thanks Charles – I reviewed your DecisionModels site – I think my sin was doing matches off-sheet. Now for my penance…

  12. @Jon — My feeds have whole posts in them, but I could see how some sites (especially those under constant attack) would want to protect their content by showing only excerpts.

  13. @Dick: thank you for clarifying my comment, this is exactly what I meant!
    @Tushar: sorry if my comment came out sounding aggressive, this wasn’t my intent! I was just pointing out what I thought (and still think) is an issue with the publishing solution you were describing.
    Re: the discussion about how much to post on a feed, I understand (and respect) why some authors would just post an excerpt on the feed, if driving visitors to the actual website is of value to the author. That being said, if I can’t see any part of the contents in my feed reader, which is the case with this post, you might as well kill the feed, because it serves no purpose at that point…

  14. I have to say iframes are almost as annoying as pop up ads and pop under ads. They mess with mouse focus and depending on the skill of the site author they often are large than the monitor so you are forced to repeatedly scroll two different places to see everything. For my money (aka time) I just skip away from iframed content onto the next thing I am interested in reading – too much effort to read!


Posting code? Use <pre> tags for VBA and <code> tags for inline.

Leave a Reply

Your email address will not be published.