# Find_in_half.py
left = 1
right = A.length
while left <= right
    mid = (left + right) / 2
    if A[mid] == key
        return mid
    else if A[mid] > key
        right = mid - 1
    else
        left = mid + 1
return -1

对于折半查找的个人理解首先对无序数组

进行排序为有序的数组

，然后采用

len()

函数得到数组

的长度，然后对该长度进行除于

的运算，在Python中即int(len(A))。这个int(len(A))也是索引值，所以数组

在这个位置的数据num的大小，令目标值target与该数值num进行比较，即target与A[int(len(A)/2)]比较大小，若

target>num

，将数值num前面的所有数据(包括num)排除，反之，则将数值num后面的所有数据(包括num)排除，再次循环折半查找，直到找到最后一个数值，若该数值仍旧不等于target，则输出False。

折半插入排序

折半插入排序工作方式折半插入排序（Binary Insertion Sort）是对直接插入排序算法的一种改进。折半插入排序与直接插入排序算法原理相同。只是，在向已排序的数据中插入数据时，采用来折半查找（二分查找）。先取已经排序的序列的中间元素，与待插入的数据进行比较，如果中间元素的值大于待插入的数据，那么待插入的数据属于数组的前半部分，否则属于后半部分。伪代码

BinaryInsertSort(A):

for i = 2 to A.length
    if A[i] < A[i - 1]
        tmp = A[i]
        low = 0
        high = i - 1
        while low <= high
            mid = (low + high) / 2
            if A[mid] > tmp
                high = mid - 1
            else
                low = mid + 1
        for j = i - 1 downto high + 1
            A[j + 1] = A[j]
        A[high + 1] = tmp

对于折半插入排序的个人理解折半插入排序结合了折半查找算法与插入排序算法的工作方式，在插入数据之前先进行折半查找，若插入的数据大于折半查找到的数据，则待插入数据将放置于折半的前置位。反之，则待插入数据将放置于折半的后置位。

代码实现

折半查找代码实现

采用

A = [41, 54, 95, 32, 11, 5, 7, 10, 21, 9, 85, 12, 13, 15, 64, 84]

简易版（待更新）

函数版

def binary_contains(gene, key_codon) -> bool:
    low: int = 0
    high: int = len(gene) - 1
    while low <= high:  # while there is still a search space
        mid: int = (low + high) // 2
        if gene[mid] < key_codon:
            low = mid + 1
        elif gene[mid] > key_codon:
            high = mid - 1
        else:
            return True
    return False


A = [41, 54, 95, 32, 11, 5, 7, 10, 21, 9, 85, 12, 13, 15, 64, 84]
my_A = sorted(A)
print(binary_contains(my_A, 21))

折半插入排序代码实现

采用

A = [41, 54, 95, 32, 11, 5, 7, 10, 21, 9, 85, 12, 13, 15, 64, 84]

简易版（待更新）

函数版

def BinaryInsertSort(mylist):
    for i in range(1, len(mylist)):
        """将当前元素暂存起来"""
        tmp = mylist[i]
        """在当前位置之前的范围查找插入"""
        low = 0
        high = i - 1
        """将范围折半再查找"""
        while low <= high:
            m = int((low + high) / 2)
            """tmp比范围中点大，范围后半段作为新的查找范围"""
            if tmp > mylist[m]:
                low = m + 1
            else:
                """tmp比范围中点小，范围前半段作为新的查找范围"""
                high = m - 1
        """此时mylist[high]的元素比tmp小"""
        j = i - 1
        """mylist[high]之后的元素往后挪一位"""
        while j >= high + 1:
            mylist[j + 1] = mylist[j]
            j -= 1
        """将tmp放在mylist[high]之后"""
        mylist[high + 1] = tmp
 
if __name__ == "__main__":
    A = [41, 54, 95, 32, 11, 5, 7, 10, 21, 9, 85, 12, 13, 15, 64, 84]
    BinaryInsertSort(A)
    print(mylist)