I am actually almost certain it has to do with people who view your page because I was thinking about this and conducted a little experiment (it's kinda confusing but bear with me).
I started off by typing every letter of the alphabet and seeing who came up on the search. So for example, I typed "A" and saw who came up. I noticed that the list of people were not necessarily in alphabetical order, but the people at the top were certainly my closest friends whose pages I visit all the time.
Then I thought maybe Facebook sets the search bar up conveniently for you to find the people you visit the most. But then I saw something strange, the girl that I just added was actually the second person in the "L" list, the first being my best friend, so that seemed odd to me.
So then I started thinking that it might actually have to do with the people who visit your page. To test the theory, I went to my "C" list, where the top two people were actually pretty much equal in terms of how many times I've visited their page and I assume they've visited mine. I went to the second person in the "C" list and clicked on their page a lot, refreshed it a few good times. Then I went back and searched "C" and sure enough, it was now the second friend whose page I had been refreshing who showed up first. I knew that this second friend was camping and had no Facebook/no way of looking at my page.
Now here's the real kicker: I told my other friend in the "C" list, the one who used to be first when I searched "C" to go on my page a couple of times. She did. I then took a couple of minutes and searched "C" again, and guess who came up first?
That's right, the girl who had just searched my page, despite the fact that I had been looking up the other girl's page recently.
Does this really prove that the Facebook search bar operates on people who have viewed your profile? Maybe, but it could also prove that I have WAY too much time on my hands.