* Module only for [ Ascending list ]
i, j = 0, len(a) # *[0, len(a)) Half open and half closed interval
''' bisect_left Left insertion position '''
while i < j:
mid = i + j >> 1
if a[mid] < target: i = mid + 1 # Increasing < i The relationship between the three , First judge less than
else: j = mid
return i
''' bisect_right Right insertion position '''
while i < j:
mid = i + j >> 1
if a[mid] > target: j = mid # First judge whether it is greater than
else: i = mid + 1
return i
from bisect import *
a = [1, 2, 6, 6, 6, 8] # Ascending
bisect_left(a, 4) # Insertion position 2, The corresponding element 6
bisect(a, 4) # ditto
bisect_left(a, 6) # ditto
bisect(a, 6) # Insertion position 5, The corresponding element 8
Goals exist , Left is the leftmost x; Right is the rightmost x My right neighbor ;
The goal doesn't exist , The left and right are the same , Are element positions larger than the target .
* distinguish ： Insert position and target position
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
return bisect_left(nums, target)
# Right lookup is different when the target exists , There are no repeating elements , Right insertion position - 1 = Left insertion position
i = bisect_right(nums, target)
return i-1 if nums[i-1] == target else i
class Solution:
def targetIndices(self, nums: List[int], target: int) -> List[int]:
nums.sort()
i = bisect_left(nums, target)
j = bisect_right(nums, target)
return list(range(i, j))
file
Source code ： Lib/bisect.py
bisect, It's the realization of Two points (bisection) Algorithm Module , The sequence order can be kept unchanged Binary search and insert .
import bisect
dir(bisect)
bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
If x Already in a In existence , Then the insertion point will be before the existing element （ On the left ）.
The left half all(val < x for val in a[lo : i])
Right half all(val >= x for val in a[i : hi])
bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)
bisect.bisect(a, x, lo=0, hi=len(a), *, key=None)
The insertion point returned is a Element already exists in x The right side of the .
The left half all(val <= x for val in a[lo : i])
Right half all(val > x for val in a[i : hi])
bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)
Place... In sorted order x Insert into a in .
This function first runs bisect_left() To locate an insertion point . then , It will be a Up operation insert() Method to insert in the correct position x To maintain the sort order .
bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)
bisect.insort(a, x, lo=0, hi=len(a), *, key=None)
hold x Insert into a Element already exists in x The right side of the .
stay a Up operation insert() Method to insert in the correct position x To maintain the sort order .
To support inserting records in a table, the key function (if any) is applied to x for the search step but not for the insertion step.
key specifies a key function of one argument that is used to extract a comparison key from each element in the array. To support searching complex records, the key function is not applied to the x value.
If key is None, the elements are compared directly with no intervening function call.
Dichotomy is very efficient for searching a range of values . For positioning specific values , The performance of the dictionary is better .
Be careful , Use bisect Before the module method , The operation object is required to be Ordered sequence （ l 、 drop ）.
In the sequence a Find the appropriate element in the dichotomy x Insertion position , Guarantee a Still an ordered sequence .
lo and hi Is an optional parameter , Define the search range respectively / Returns the of the index Upper and lower limits , By default, the default is for Whole Sequence lookup .
therefore , Returned location index Also known as “ The insertion point ”, Set it to i, Then the sequence a It can be divided into two parts , The slice represents the left side a[lo, i) And the right side a[i, hi] .
"""Bisection algorithms."""
def insort_right(a, x, lo=0, hi=None, *, key=None):
"""Insert item x in list a, and keep it sorted assuming a is sorted. If x is already in a, insert it to the right of the rightmost x. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. """
if key is None: lo = bisect_right(a, x, lo, hi)
else: lo = bisect_right(a, key(x), lo, hi, key=key)
a.insert(lo, x)
def bisect_right(a, x, lo=0, hi=None, *, key=None):
"""Return the index where to insert item x in list a, assuming a is sorted. The return value i is such that all e in a[:i] have e <= x, and all e in a[i:] have e > x. So if x already appears in the list, a.insert(i, x) will insert just after the rightmost x already there. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. """
if lo < 0: raise ValueError('lo must be non-negative')
if hi is None: hi = len(a)
# Note, the comparison uses ">" to match the
# __lt__() logic in list.sort() and in heapq.
if key is None:
while lo < hi:
mid = (lo + hi) // 2
if a[mid] > x: hi = mid
else: lo = mid + 1
else:
while lo < hi:
mid = (lo + hi) // 2
if key(a[mid]) > x: hi = mid
else: lo = mid + 1
return lo
def insort_left(a, x, lo=0, hi=None, *, key=None):
"""Insert item x in list a, and keep it sorted assuming a is sorted. If x is already in a, insert it to the left of the leftmost x. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. """
if key is None: lo = bisect_left(a, x, lo, hi)
else: lo = bisect_left(a, key(x), lo, hi, key=key)
a.insert(lo, x)
def bisect_left(a, x, lo=0, hi=None, *, key=None):
"""Return the index where to insert item x in list a, assuming a is sorted. The return value i is such that all e in a[:i] have e < x, and all e in a[i:] have e >= x. So if x already appears in the list, a.insert(i, x) will insert just before the leftmost x already there. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. """
if lo < 0: raise ValueError('lo must be non-negative')
if hi is None: hi = len(a)
# Note, the comparison uses "<" to match the
# __lt__() logic in list.sort() and in heapq.
if key is None:
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x: lo = mid + 1
else: hi = mid
else:
while lo < hi:
mid = (lo + hi) // 2
if key(a[mid]) < x: lo = mid + 1
else: hi = mid
return lo
# Overwrite above definitions with a fast C implementation
try:
from _bisect import *
except ImportError:
pass
# Create aliases
bisect = bisect_right
insort = insort_right
