Oh, it means log base; I thought it meant log squared. Sorry.
I think you are mistaken about q1, but I think
binary search is correct for q2; it runs in logarithmic time. Do some Googling for search algorithms, and you find all sorts of things. A few I think actually useful follow:
1 2 and you can probably find other algorithms and structures on the same university website, maybe even one about links. I think those two links will answer all your questions for q2.