Optimal algorithm for finding the odd sphere with a balance scale
This looks like a generalization of the classic $12$ ball problem.
You should be able to modify Jack Wert's wonderful algorithm, (which was designed for the case when $N= \dfrac{3^m - 3}{2}$) to work for any $N$. I believe I had made an (incomplete) attempt when someone asked this on stackoverflow.
Note that the numbers $\dfrac{3^m - 3}{2}$ are special, in the sense that they are the turning points.
In the variant of the problem where you are also required to tell if the odd sphere is heavier or lighter, for $\dfrac{3^m -3}{2} \lt N \le \dfrac{3^{m+1}-1}{2}$, the optimal number of weighings can be shown to be $m+1$.
If you are only required to find the odd sphere and not necessarily figure out if it is heavier or lighter, the turning points are $\dfrac{3^m -3}{2} + 1$.
For a complete treatment, we have to consider all the combinations with some variant parameters. The base problem: given $n$ balls, one being "deviant" (not the same weight than the $n-1$ others), how to find the deviant ball in at most $w$ weighs ? Or, similarly, what is the maximum number $n$ of balls for which the deviant ball can always be identified in at most $w$ weighs ?
The variant parameters are:
The balls may be "marked". A ball which is "marked heavy" may be deviant by being heavier, but not lighter. We can consider a variant problem where all balls are individually marked heavy or light (independently of each other). The problem in which you know a priori that the deviant ball is heavier is a subcase of the "marked balls" problem (i.e. it is the "marked balls" problem where all balls are marked "heavy").
You may be asked to identify the deviant ball and to give its deviance direction (i.e. you also need to find out whether the deviant ball is heavier or lighter).
Possibly, an extra "standard" ball is given, guaranteed to be non-deviant.
We'll first see the "marked balls" problem because it is an essential step of the full treatment.
Marked balls
First, some important notes:
With marked balls, identifying the deviant ball implies identifying the deviance, automatically.
If you have only one marked ball, then the problem is solved with no weigh at all: if there is only one suspect, then it is the culprit.
If you have two marked balls and they bear distinct marks (one is marked heavy, the other is marked light), then the problem is unsolvable -- unless you have a standard ball available, in which case you just have to make a weigh between that standard ball and one of the potentially deviant balls.
Each weigh may yield only 3 different results, so with $w$ weighs you may reach at most $3^w$ distinct conclusions. Thus, the problem cannot be solved (reliably) if $n \gt 3^w$.
It so happens that the "marked balls" problem can be solved for all $n$ up to that $3^w$ limit (assuming the presence of a standard ball if $n = 2$). This is demonstrated with the following recurrence:
With $w = 0$ (no weigh at all), you may indeed solve the problem with $n = 3^0 = 1$ marked ball.
With $w = 1$ and two marked balls with the same mark, just weigh one against the other; if they have distinct marks, use the extra standard ball, as explained above.
If $w = 1$ and three marked balls, then two of them (at least) have the same mark. Weigh one against the other; this yields the result.
If $w \gt 1$ and $3^{w-1} \lt n \leq 3^w$, then you can assemble two sets of balls of size $\lceil n/3 \rceil$, taking care to put the same number of "heavy" marks in both sets (which implies that you also put the same number of "light" marks in both sets). Then weigh one set against the other. If the balance tilts to the left, then the deviant ball is one of "heavy" balls from the left scale or one of the "light" balls from the right scale. If the weigh result is balanced, then the deviant ball is in the set of balls which you put in neither set. Either way, you end up with at most $3^{w-1}$ suspect balls, $w-1$ weighs, and at least one ball which is definitely non-deviant, i.e. a "standard ball". Recurrence applies.
Unmarked balls
Consider $n$ unmarked balls. Your first weigh will result in either a balanced result, or an unbalanced result. If the result is balanced, then the problem is reduced to that of $w-1$ allowed weighs with all the balls that did not take part into the first weigh; and the balls used in the first weigh are now known to be all "standard balls". If the result is unbalanced, then all balls involved in the weigh are suspect but can all be marked, so this brings us back to the problem of marked balls (and the balls which were not used in the first weigh are now known to be standard).
Let's call $f(w)$ the maximum number of unmarked balls which can be processed in $w$ weighs, assuming that an extra standard ball is available. For now, we suppose that we want to identify both the ball and its deviance.
$f(1) = 1$. Indeed, with only one weigh, you get only three conclusions, so you cannot process two balls, because two balls mean four possible conclusions (first ball is heavy, first ball is light, second ball is heavy, second ball is light). With one ball, you just weigh it against the extra standard ball.
If $w \gt 1$ and you have $n \gt f(w-1)$ balls, then isolate $f(w-1)$ balls, and split the remainder into two subsets of equal size (if there is an odd number of remaining balls, add the standard ball). Do a weigh between these two subsets. If a balanced result is obtained, then recurrence applies (you have $f(w-1)$ unmarked balls and $w-1$ weighs). If an unbalanced result is obtained, then all the balls involved in the first weigh are now "marked" (except of course the extra standard ball, if it was added). This leads us to the following relation: $f(w) = f(w-1) + 3^{w-1}$.
Thus, $f(w) = (3^w - 1)/2$ (you can verify it fulfills the recurrence relation and the starting point $f(1) = 1$).
What if you don't have an extra standard ball to begin with ? Then you will not be able to make the first weigh with $3^{w-1}$ balls, since that's an odd integer, and a weigh involves an even number of balls. So you have to use only $3^{w-1}-1$ balls. However, after this first weigh, you have one or several "standard balls", so you are back to the previous problem. Thus, unavailability of an extra standard ball means just decrementing by one the maximum number of processable balls.
What if you are not interested in identifying the actual deviance direction, but just in finding out which ball is deviant ? Then all of the above still holds, except for the starting point. If you call $g(w)$ the maximum number of unmarked balls which you can process under these conditions, then $g(1) = 2$: with two balls, just weigh one against the extra standard ball; with three balls, you have to include two suspect balls in the first weigh, but you will not known which is the culprit since they are unmarked. It follows that $g(w) = f(w) + 1$ for all $w$.
Conclusion
If you are allowed $w$ weighs, then you can find the deviant ball and its deviance among a maximum of $(3^w-3)/2$ balls. If you are not interested in the deviance direction but only in identifying the deviant ball, then you can process one extra ball. If a "standard" extra ball is available, then you can process one extra ball. These two "one extra ball" increments are cumulative; thus, with 3 weighs, you can process up to 12, 13 or 14 balls, depending on whether you have an extra standard ball, and whether you are interested in the deviance direction.
Extra conditions: if no "standard" extra ball is provided, then the problem is unsolvable if:
there are one or two balls and you want the deviance direction;
there are exactly two balls and you are not interested in the deviance direction.
Apart from these two edge cases, all number of balls no greater than the maximum can be processed (there is no "hole").
If $N = 3^n$ is a power of three, then we can do it $n+1$ weighings:
First, assume that the odd ball is heavier than the others (this is just to simplify the exposition; we will come back to this). Now label all the balls from $0$ to $N-1$, in ternary notation. For each ternary digit position, weigh all the balls with $0$ in that position against all the balls with $2$ in that position, leaving out the remaining balls (with 1 in that position). The result tells you (assuming that the odd ball is heavier) the ternary digit of the odd ball in that position: $0$ if the $0$'s outweigh the $2$'s; $2$ if the $2$'s outweigh the $0$'s; and $1$ if they are equal.
So now you have the ternary expansion of the odd ball, assuming that it's heavy. If that assumption is wrong, and the odd ball is light, then the number of the odd ball is obtained by flipping all the $0$'s to $2$ and vice versa. To find out which of these two candidates is the odd ball, just weigh one of them against a ball that is known not to be odd.
This doesn't work if $N$ is not a power of three, because in general the number of balls with $0$ in a given position is not the same as the number of balls with $2$ in that position. So we can't weigh them against each other. But we can fix this by the simple device of splitting the balls into two equal heaps, numbering one heap upwards from $0$ and the other heap downwards from $3^n-1$, where $3^n$ is the smallest power of three that is $\ge N$. (If the number of balls is odd, label the left-over ball with $11...11$.)
My guess is that this procedure is optimal when $N$ is a power of three, but otherwise we can sometimes do better; for instance, if $N=4$, we only need two weighings to identify the odd ball (but we won't always know whether it is heavier or lighter).
Edit This solution shows how to solve the problem in $n$ weighings for any $N \le 3^n$ when we know whether the odd ball is heavier or lighter. Now we can put this together with Moron's proposed solution (linked to in Moron's answer) to get a complete solution in $n$ weighings when $N \le (3^n-3)/2$. (This solution also tells us whether the odd ball is heavier or lighter.)