二分查找

说明：元素必须是有序的，如果是无序的则要先进行排序操作。

基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；

注意点

折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

时间复杂度

1. 二分查找是有条件的，首先是有序，其次因为二分查找操作的是下标，所以要求是顺序表
2. 最优时间复杂度：O(1)
3. 最坏时间复杂度：O(logn)

Python实现

# 递归方式
def binary_search1(alist, data):
    length = len(alist)
    if length < 1:
        return -1
    mid = length // 2
    if alist[mid] > data:
        return binary_search1(alist[:mid], data)
    elif alist[mid] < data:
        return binary_search1(alist[mid + 1:], data)
    else:
        return mid


# 非递归方式
def binary_search2(alist, data):
    length = len(alist)
    first = 0
    last = length - 1
    while first <= last:
        mid = (last + first) // 2
        if alist[mid] > data:
            last = mid - 1
        elif alist[mid] < data:
            first = mid + 1
        else:
            return mid
    return -1


dest = [5, 2, 7, 4, 8, 1, 6, 3]
data = sorted(dest)
result = binary_search1(data, 3)
print(result)

dest = [5, 2, 7, 4, 8, 1, 6, 3]
data = sorted(dest)
result = binary_search2(data, 3)
print(result)

C语言实现

#include<stdio.h>

//二分查找，非递归方式
int BinarySearch1(int a[], int value, int n)
{
    int low, high, mid;
    low = 0;
    high = n-1;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            high = mid-1;
        if(a[mid]<value)
            low = mid+1;
    }
    return -1;
}

//二分查找，递归版本
int BinarySearch2(int a[], int value, int low, int high)
{
    int mid = low+(high-low)/2;
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return BinarySearch2(a, value, low, mid-1);
    if(a[mid]<value)
        return BinarySearch2(a, value, mid+1, high);
}


int main()
{
    int a[] =  {1,2,3,4,5,6,7,8};
    int val = 3;

    int result1 = BinarySearch1(a, 3, 8);
    printf("得到的结果是%d\n", result1);

    int result2 = BinarySearch2(a, 3, 0, 8);
    printf("得到的结果是%d\n", result2);

    return 0;
}