Count numbers less than $K$ in array
Here is a $O(1)$ solution after $O(n)$ preprocessing step, assuming that all elements are less than some number $C$ (in your case $10^5$) in pseudocode 

count = new int[C] (array of integers)
for every a[i] in a  
   count[a[i]]++
for i = 1, i &lt; C, i++  
   count[i] += count[i-1] 


To Answer a query for a given k you just return count[k - 1]