When it is said:
Routing table lookup in a line rate, why is line rate important when the router still needs to perform a linear search in the size of routing table? Is there a relationship between line rate and routing table lookup?
First, it is unlikely that a router performs a linear search of a linear routing table. That may have been true by some vendors many years ago, but there are things like TCAM, tree, trie, hash table, etc. that are many orders of magnitude faster than what you describe.
A device that can perform at wire-speed (line rate) is the goal. It means your traffic is not slowed. That really requires some sort of hardware acceleration.
Many switches can switch at, or very near, wire-speed because most switching is done in hardware.
Routing is more problematic because there are more things involved (QoS, NAT, ACLs, etc.). Pure, simple routing may be able to approach wire-speed, but adding other services can greatly slow the routing. The slower the line rate, the closer a router will come to routing at the line rate. For instance, a modern router with interfaces at 10 Mbps could probably route at, or near, the line rate, but a router with 1 or 10 Gbps interfaces that can run close to the line rate will be very expensive.