# Computer Algorithms: Interpolation Search

## Overview

I wrote about binary search in my previous post, which is indeed one very fast searching algorithm, but in some cases we can achieve even faster results. Such an algorithm is the “interpolation search” – perhaps the most interesting of all searching algorithms. However we shouldn’t forget that the data must follow some limitations. In first place the array must be sorted. Also we must know the bounds of the interval.

Why is that? Well, this algorithm tries to follow the way we search a name in a phone book, or a word in the dictionary. We, humans, know in advance that in case the name we’re searching starts with a “B”, like “Bond” for instance, we should start searching near the beginning of the phone book. Thus if we’re searching the word “algorithm” in the dictionary, you know that it should be placed somewhere at the beginning. This is because we know the order of the letters, we know the interval (a-z), and somehow we intuitively know that the words are dispersed equally. These facts are enough to realize that the binary search can be a bad choice. Indeed the binary search algorithm divides the list in two equal sub-lists, which is useless if we know in advance that the searched item is somewhere in the beginning or the end of the list. Yes, we can use also jump search if the item is at the beginning, but not if it is at the end, in that case this algorithm is not so effective.

So the interpolation search is based on some simple facts. The binary search divides the interval on two equal sub-lists, as shown on the image bellow.

What will happen if we don’t use the constant ½, but another more accurate constant “C”, that can lead us closer to the searched item.

# From SVG to Geo Coordinates – A Complete Guide

## Why This Task Is Not Trivial?

First of all what do we have? There is a vector shape, which may represent a map, which we’d like to convert into a GEO map. In other words there is a SVG file containing the source shape, that you’d like to convert in geoJSON or whatever collection of geo points. This is not trivial, of course, first of all because there’s no an algorithm or automation that can do this, and because everybody knows that the resulting map will be only approached, but will never be so accurate as the vector shape. This is because in a vector shape you may contain Bézier Curves, which I’ll show a little bit later in this post, that are difficult to represent in geo coordinates.

So the first task will be to find an approaching algorithm. However there are two things that are optimistic:

1. You can’t effectively represent Bézier curves in geo coordinates, but even if you could do it there’s no practical need, because the collection of geo coordinates will be huge and this will slow down you’re application. Remember that geoJSON is yet again possibly used by your browser and the amount of geo points will be proportionally slowing down the app.
2. As you may know Google’s visualization map is representing the World’s countries again with quite approached maps. Take a look at the following image – the country borders are quite sharpened:

So far we know that we need an approaching algorithm that will convert vector lines and possibly curves in geo coordinates, but before we proceed we’ve to understand the SVG format. Continue reading From SVG to Geo Coordinates – A Complete Guide