Teaching Kids Programming: Videos on Data Structures and Algorithms
If a list/array sorted, we can find the insertion point/index of given value x via Binary Search Algorithm – which takes O(LogN) time. In Python, we have bisect_left and bisect_right from the package bisect library.
bisect_left
The bisect_left has the following function signature:
1 | bisect_left(a, x, lo=0, hi=None, key=None) |
bisect_left(a, x, lo=0, hi=None, key=None)
It returns the insertion point i where all elements at a[:i] is strictly smaller than x and all elements at a[i:] are bigger or equal then x. The lo and hi are optional parameters to specify the lower/upper index. The key can be also passed to give a customize key function:
If we go for the linear search, it will take O(N):
1 2 3 4 5 6 7 8 9 10 11 12 13 | def bisect_left(a, x, lo=0, hi=None, key=None): if lo < 0: raise ValueError('lo must be non-negative') if hi is None: hi = len(a) for i in range(lo, hi): if key is None: v = a[i] else: v = key(a[i]) if a[i] >= x: return i return hi |
def bisect_left(a, x, lo=0, hi=None, key=None):
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
for i in range(lo, hi):
if key is None:
v = a[i]
else:
v = key(a[i])
if a[i] >= x:
return i
return hiAs the array is already sorted, we can binary search – this improves the time complexity to O(LogN).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def bisect_left(a, x, lo=0, hi=None, key=None): if lo < 0: raise ValueError('lo must be non-negative') if hi is None: hi = len(a) while lo < hi: mid = (lo + hi)//2 if key is None: v = a[mid] else: v = key(a[mid]) if a[mid] < x: lo = mid+1 else: hi = mid return lo |
def bisect_left(a, x, lo=0, hi=None, key=None):
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo + hi)//2
if key is None:
v = a[mid]
else:
v = key(a[mid])
if a[mid] < x:
lo = mid+1
else:
hi = mid
return lobisect_right
The bisect_right takes the same parameters but behaves differently. It will return a insertion point i where all elements at a[:i] are smaller or equal to x and all elements at a[i:] are strictly larger than x:
The linear version is quite similar than above:
1 2 3 4 5 6 7 8 9 10 11 12 13 | def bisect_right(a, x, lo=0, hi=None, key=None): if lo < 0: raise ValueError('lo must be non-negative') if hi is None: hi = len(a) for i in range(lo, hi): if key is None: v = a[i] else: v = key(a[i]) if a[i] > x: return i return hi |
def bisect_right(a, x, lo=0, hi=None, key=None):
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
for i in range(lo, hi):
if key is None:
v = a[i]
else:
v = key(a[i])
if a[i] > x:
return i
return hiand the optimal Binary Search implementation of bisect_right:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def bisect_right(a, x, lo=0, hi=None, key=None): if lo < 0: raise ValueError('lo must be non-negative') if hi is None: hi = len(a) while lo < hi: mid = (lo + hi)//2 if key is None: v = a[mid] else: v = key(a[mid]) if a[mid] > x: hi = mid else: lo = mid + 1 return lo |
def bisect_right(a, x, lo=0, hi=None, key=None):
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo + hi)//2
if key is None:
v = a[mid]
else:
v = key(a[mid])
if a[mid] > x:
hi = mid
else:
lo = mid + 1
return lo–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Top Down and Bottom Up Dynamic Programming Algorithm to Type N letters on a 2-keys Keyboard
Next Post: Teaching Kids Programming - Greedy Algorithm to Find Longest Increasing Subsequence in O(NLogN) via Binary Search
