Menu
What is a Pythonic way to search or manipulate sorted sequence?
497
The idea is to find the pivot point, divide the array into two sub-arrays and perform a binary search. For a sorted (in increasing order) and rotated array, the pivot element is the only element for which the next element to it is smaller than it. Using binary search based on the above idea, pivot can be found.
Interpolation and Quadratic Binary Search. If we know nothing about the distribution of key values, then we have just proved that binary search is the best algorithm available for searching a sorted array.
Given a sorted array of integer numbers, write a function which returns zero-based position on which the specified value is located. Function should return negative value if requested number cannot be found in the array. If value occurs more than once, function should return position of the first occurrence.
bisect is part of the standard library - is that the sort of thing you're looking for?
155
It's worth noting that there are a couple high-quality Python libraries for maintaining a sorted list which also implement fast searching: sortedcontainers and blist. Using these depends of course on how often you're inserting/removing elements from the list and needing to search. Each of those modules provide a SortedList class which efficiently maintains the items in sort order.
From the documentation for SortedList:
L.bisect_left(value) Similar to the bisect module in the standard library, this returns an appropriate index to insert value in L. If value is already present in L, the insertion point will be before (to the left of) any existing entries. L.bisect(value) Same as bisect_left. L.bisect_right(value) Same as bisect_left, but if value is already present in L, the insertion point will be after (to the right of) any existing entries. Both implementations use binary search to find the correct index of the given value. There's a performance comparison page for choosing between the two modules.
Disclaimer: I am the author of the sortedcontainers module.
43
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
