Question entretien chez Microsoft : Write a code for finding a certain element in an unsorted array assuming element definitely exists. How can we improve the efficiency?

Microsoft

Write a code for finding a certain element in an unsorted array assuming element definitely exists. How can we improve the efficiency?

Utilisateur anonyme

9 oct. 2012

O(n) ia always smaller than O(nlogn)+O(logn). hence linear search will always be efficient

Utilisateur anonyme

17 oct. 2009

i think the simplest way to solve is to scan it once, it will have O(n) complexity well any other answers?

Utilisateur anonyme

12 nov. 2009

it's O(n) to improve efficiency sort it first : O(nlgn) then every look-up becomes O(lgn)