Selected Writings

Quick Sort

def quick_sort(nums, l, r):
    if l >= r:
        return
    pivot = nums[(l+r)>>1]
    i, j = l, r
    while i < j:
        # i += 1
        # j -= 1
        while nums[i] < pivot:
            i += 1
        while nums[j] > pivot:
            j -= 1
        if i < j:
            nums[i], nums[j] = nums[j], nums[i]
    quick_sort(nums, l, j)
    quick_sort(nums, j + 1, r)

Binary Search

"""
如果if (check(mid)) 条件成立，首先考虑一下答案在左区间还是右区间，
如果答案在左区间并且mid也可能是答案，那么就要按[l, mid], [mid + 1, r]来划分；
如果答案在右区间并且mid也可能是答案，那么就要按[l, mid - 1], [mid, r]来划分。
o for check(true), . for check(false), v for target

search_1 is only applicable for below scenario
................vooooooooo

search_2 is only applicable for below scenario
oooooooov...................
"""
def search_1(l, r):
	mid = (l + r) >> 1
	if check(mid):  # if after check, array becomes [l, mid] and [mid + 1, r]
		r = mid
	else:
		l = mid + 1
	return l  # return r also works since l == r

def search_2(l, r):
	mid = (l + r + 1) >> 1
	if check(mid):  # if after check, array becomes [l, mid - 1] and [mid, r]
		# in other words, mid itself doesn't satify the answer
		l = mid
	else:
		r = mid - 1
	return l  # return r also works since l == r