For example, if your problem is looking up elements in a dictionary (key-value) structure, there are many ways to do it. A hash table? Binary tree? B-tree? Sorted array? Trie? Patricia trie? Linear search in a linked list? Linear search in an array? Are the arrays fixed sized, or variable sized vectors? All of these solutions may be correct, depending on other factors, and all of them have many variants.
And that, of course, assumes that you know that a dictionary structure is what you need. Maybe your problem actually would call better for a table with GiST indexes, or a quadree dividing up a two-dimensional space.
Above that level, even if your data structure needs are fairly simple or fairly well determined, there's how you structure and organize your code to minimize the chance of bugs, make it extensible, and make it understandable to future programmers. Most of my work isn't writing fresh code. It's finding and fixing bugs in existing code, and extending it to do new things it was never intended to do. Depending on how well organized it is, and how expressive the code is of its intent, that job can be much more difficult or much easier.
That's where a lot of the creativity comes in. Finding the write way to structure and express your code to fit the problem at hand. Writing code that will be adaptable to the future, easy to extend without introducing new bugs, easy to fix bugs in, but without including a lot of extra machinery for features that you will never need. It is easy to write code that does a single task, but will be fragile if someone ever tries to extend it to do something else. It is also easy to spend all of your time writing AbstractFactoryIteratorFunctionFactoryAbastractGenerators which are infinitely modular and extensible but don't actually solve any problems.
Great code is code which solves a real problem, and can be used tomorrow to solve five more problems that you didn't even know about today, but which doesn't suffer under the weight of being designed to be extended in ways that you thought might be useful later, but wind up never being so. And writing such software, and modifying in those five ways, takes a substantial amount of creativity.
In creative writing you express your thoughts using any of the human's natural language and in programming you do the same using a programming language and both requires logical and creative thinking. Just that in programming you can see your thoughts coming to life which makes it much more cool.
When asked to say, draw a picture of this house, most trained artists, who have learnt the mechanics should be able to do a faithful rendition of that house. The same with a small program, most trained programmers will be able to make it, using their skills.
However, where both great artists and great programmers are the same is that they bring something more than the sum total of the parts to their work. This something more is what cannot be taught.
It takes an all too infrequent approach to teaching how to edit and actually shows the before-and-after work of great authors. In this case, the reader sees quite a bit of Fitzgerald's process deconstructed. Having seen the changes required of the first draft, it left me with much higher hopes for leveling up my own writing.
You do have some sense of what you are about to write. But it's not that clear. You are not exactly sure what the program will turn out to be until you sit down to start writing. Like writing, rampant thoughts pull you in multiple directions until one seduces you into following it.
It's surprising how seemingly irrelevant factors affect the program. A recent conversation with a non-programmer, a change in the weather, where you are sitting, or music are enough to set you off in a different direction. If a sense of design isn't precisely what shapes a program, a programmer would do well to pretend that it is.
The counterpoint to the binary search analogy is that there are infinite ways to avoid writing a program that needs a binary search and write a different program instead.
Basically, fiction authors are writing obfuscated C, but doing so in Python, where the interpreter was compiled for a version of DOS intended for Windows 3.1 but coaxed to work on WINE, set inside of a virtual machine on custom-built ARM hardware with propriety drivers, with nothing but the AppleTalk protocol provided for communication between the author and the reader. If we get a buffer overflow in that environment, then we win.