Timeline for Searching an element in a sorted array
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 19, 2011 at 16:45 | history | migrated | from stackoverflow.com (revisions) | ||
| Mar 14, 2010 at 23:56 | comment | added | Carl Manaster | @Larry, you remind me why I stopped reading C and C++ newsgroups long, long ago. | |
| Mar 14, 2010 at 19:34 | comment | added | Larry Watanabe | If you read his post, it was supposed to be implemented in either C++ or C, and he chose C. so any C++ specific comments wouldn't be relevant. | |
| Mar 14, 2010 at 14:05 | comment | added | Carl Manaster | Thanks, @UncleBens - that's what I meant when I said my STL was rusty; std::equal_range would make a simple one-liner of this whole question, I think. Good call. | |
| Mar 14, 2010 at 11:23 | comment | added | UncleBens |
Or just use std::equal_range
|
|
| Mar 14, 2010 at 1:43 | comment | added | Carl Manaster | @James: Or incorporate std::upper_bound, too, then subtract them. If my rusty STL is right, at least. | |
| Mar 14, 2010 at 1:35 | comment | added | James McNellis |
@Micky: If you are using C++, look at std::lower_bound. If the iterator returned by the search points to the value you searched for, you know that value is in the container. You can then walk forward and count the number of instances of that value in the container.
|
|
| Mar 14, 2010 at 1:33 | comment | added | Ed Swangren | I disagree. Most coding tests require that you do not use standard library functions. If I were the tester I would state that explicitly; using a std::vector does not tell me anything about what you can do. | |
| Mar 14, 2010 at 1:33 | comment | added | President James K. Polk | Maybe, but then it is a trick question. If he'd used the STL, someone else would say that it proves he doesn't really understand the basic algorithms of CS and would be lost if he needed something that wasn't in the STL. | |
| Mar 14, 2010 at 1:30 | comment | added | Micky | Argh. I think there's a binary search algorithm but not a "count the number of instances" part. And more importantly it wouldn't return the 1st index as well. Anyways, I'll take another look. But thanks anyways! It will be something I have to think about for my next job app. | |
| Mar 14, 2010 at 1:23 | history | answered | Carl Manaster | CC BY-SA 2.5 |