Comment by mining

I would probably argue that either the first algorithm is incorrect (because searched can be larger than INT_MAX) or the complexity of the second algorithm is bound both by O(searched) (or sqrt(searched), if implemented with more vigour) and O(1) (because the value of 'searched' is bound by a constant).