简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return
[-1, -1].
For example,
Given
return
» Solve this problem
Given
[5, 7, 7, 8, 8, 10] and target value 8,return
[3, 4].
O(n), not O(logn)
ReplyDeleteWe do binary search here. So it should be O(logn)
Delete你这个解法显然是错的，worst case O(n), not O(logn)
DeleteWorst case is not O(logn). Assume all 1s
ReplyDeleteWe can do binary search twice. One is to find the most left index of the target and the other is the most right index of that. In this way, the worst case should be O(logn) but the code is not clean.
ReplyDelete