Explain some Linear Search optimization techniques

Technology CommunityCategory: SearchingExplain some Linear Search optimization techniques
VietMX Staff asked 3 years ago

If the elements you would be searching in a list are NOT uniformly distributed, then you could do certain optimizations that can help you improve the efficiency of your search algorithms. For such improvements to be effective, you do need to know the characteristics of the data being searched, the frequency and also the fact that the underlying collection needs to be modifiable.

  1. Most used pattern: If the likelihood of the current element being searched again is high, then move if from it’s current location (say position i) to the front of the collection (say position 0). This does require moving elements from A[0, i-1] to A[1, i] to accommodate the new element at A[0].
  2. The disadvantage of the above pattern is that it requires a lot of movement. One quick strategy is to move an element up on success by simply swapping the target element from position x with the first element at position 0. This eventually results in a similar pattern as the frequently searched elements bubble up to the top of the list.
  3. On the other end of the spectrum, if an element is unlikely to be search again, then moving it to the end on find improves the chances of the other elements being searched.