While stack != value & startIndex stack then return middle + mod1 Middle = Math.floor( (stopIndex+startIndex)/2 ) # Use bisection (binary search) to find leftmost or rightmost border indexes GetRangeBorderIndexes = (stack, start, end) ->Īr = getBorder( stack, start, "left" ) (Coffeescript) # Search ordered array for timestamps falling between 'start' & 'end' I could loop through the array and do a comparison, but is there a more efficient way? Given the above example, what is the most efficient way of finding the index of the first and last timestamps that fall between the startTime and endTime?Ī correct script would discover and return indexes 1 & 4 ( timestamps, timestamps) A simplified example would look something like: timestamps = I need to grab the subset of the array that falls between a start and end time. So we can see, that as the number of searches we want to perform on the array starts to approach n, sorting first becomes a decent option.Īnother possible option for repeated searches, is constructing a hash table, O(n), which has average run time of O(1) for searches.I have an array of sequential timestamps.
On the other hand, sorting once, O(n log n), with n binary searches, O(n log n), would have a total worst case run time of O(n log n). If we assume we needed to search the array n times the total worst case run time of the linear searches would be O(n^2)).
A typical sorting algorithm like merge sort will have a worst case running time of O(n log n) and each binary search will be O(log n). However, if you will need to perform a search on the list several times it may be worth while to sort the list, then use binary search on the list for each search. The worst case running time for this is O(n) If the numbers are not sorted then you can do a linear search, which looks at every value one by one. If the values were not sorted we would not know whether our desired value was within the choices to the right, and as such we could not eliminate those choices. If our guess gives us a value > than our desired value, then we know the choices to the right of it can not contain our value, because the values are sorted. It needs to be sorted, in order for us to correctly eliminate half the choices at each step. Here is modified pseudocode for binary search that handles the case in which the target number is not present:īinary search only works on sorted lists. In general, once max becomes strictly less than min, we know that the target number is not in the sorted array. There are no such numbers! At this point, we can conclude that the target number, 10, is not in the primes array, and the binarySearch function would return -1. What does it mean for min to equal 4 and max to equal 3? It means that the only possible guesses are at least 4 and at most 3. With both min and max equaling 4, the guess must be index 4, and primes is greater than 10.
The guess is then index 3 (since (3 + 4) / 2 equals 3.5, and we round down), and primes is less than 10, so that min becomes 4. If you trace out the index values for min and max as the binarySearch function executes, you would find that they eventually get to the point where min equals 3 and max equals 4. If it were there, 10 would be between the values 7 and 11, which are at indices 3 and 4. In our example, suppose that we're searching for the target number 10 in the primes array. The target number isn't in the array if there are no possible guesses left.
0 kommentar(er)
