Hacker News Reader

Comment by lalitmaganti | Hacker News Reader

I also wrote recently [1] about Exponential Search [2] which is another algorithm if you need to repeatedly binary search in an array where the elements you're searching are themselves are sorted. It allowed for an 8x speedup in our workload!

[1] https://lalitm.com/post/exponential-search/ [2] https://en.wikipedia.org/wiki/Exponential_search

View on HN

Exponential search is useful when you're querying a REST API that addresses resources with sequential IDs, and need the last ID, but there's no dedicated endpoint for it:

  HEAD /users/1 -> 200 OK
  HEAD /users/2 -> 200 OK
  HEAD /users/4 -> 200 OK
  ...
  HEAD /users/2048 -> 200 OK
  HEAD /users/4096 -> 404 Not Found

And then a binary search between 2048 and 4096 to find the most recent user (and incidentally, the number of users). Great info to have if you're researching competing SaaS companies.

I'm guessing you don't really do this for users since the response for all of them should be 401 on any user that you aren't logged in as? I would argue even for IDs that don't exist, you should get the same error whether they don't exist or you just aren't authorised to see them. It's been a few years since I worked in web but I think that's what I would have done, GitHub does similar for private repos.

Reply on news.ycombinator.com