社区 › 研发应用 › [google面试题]Given 
a
 sorted
 array
 of
 integers,
how 
can
 you
 find
 the
 location
 of
 a
 particular 
integer
x?

季良 发表于 2013-7-30 13:46:30

[google面试题]Given 
a
 sorted
 array
 of
 integers,
how 
can
 you
 find
 the
 location
 of
 a
 particular 
integer
x?

宋倩倩 发表于 2013-7-30 13:55:11

Good answer:Use binary search.Compare the number in the middle of the arraywith x.If it is equal,we are done.If the number is greater,we know to look in thesecond half of the array.If it is smaller,we know to look in the first half.We can repeat the search on the appropriate half of the array by comparing the middle element of that array with x,once again narrowing our search by a factor of 2.We repeat this process until we find x.This algorithm takes O(logn) time.Not‐so‐good answer:Go through each number in order and compare it to x.Thisalgorithm takes O(n) time.

查看完整版本: [google面试题]Given 
a
 sorted
 array
 of
 integers,
how 
can
 you
 find
 the
 location
 of
 a
 particular 
integer
x?