binarySearch() 函数在有序数组中查找元素。

二分查找（Binary Search）是一种基于比较目标值和数组中间点的元素来定位目标值的搜索算法。二分查找的前提是数组已经排序。时间复杂度为O(log n)，是一种高效率的查找算法。

二分查找最常见的应用场景就是在有序数组中查找元素。对一个有序数组进行查找时，可以利用二分查找的思想，每次将待查找的区间缩小一半，直到找到目标元素或者确定目标元素不存在。

实现思路

对于一个给定的有序数组，假定要查找元素x，其数组长度为n。首先将查找区间设定为整个数组，即low=0，high=n-1。每次查找时，找到数组中间位置mid=(low+high)/2，将要查找元素与mid的元素进行比较，若x等于mid的元素，查找成功，返回mid；若x小于mid元素，则在左半个数组中查找，即将查找区间缩小为low到mid-1；若x大于mid元素，则在右半个数组中查找，即将查找区间缩小为mid+1到high。重复以上步骤，直到找到x或者确定x不存在于数组中。

代码实现

二分查找的实现有很多种方式，以下是常规实现和递归实现。在实现方式上的差异上，对算法的性能有很大的影响。

1.常规实现

//二分查找，数组a中查找元素x，数组大小为n

int binarySearch(int* a, int n, int x)

{

    int low = 0, high = n - 1;

    while(low <= high)

    {

        int mid = (low + high) / 2;

        if(a[mid] == x)

            return mid;

        else if(a[mid] < x)

            low = mid + 1;

        else

            high = mid - 1;

    }

    return -1;

}

该实现方法采用while循环构造查找过程，每次都将查找范围缩小一半，时间复杂度为O(logn)。

2.递归实现

//二分查找，数组a中查找元素x，数组大小为n

int binarySearch(int* a, int low, int high, int x)

{

    if(low > high)

        return -1;

    int mid = (low + high) / 2;

    if(a[mid] == x)

        return mid;

    else if(a[mid] < x)

        return binarySearch(a, mid + 1, high, x);

    else

        return binarySearch(a, low, mid - 1, x);

}

该实现方法采用递归的方式实现二分查找，每次都将查找范围缩小一半，时间复杂度为O(logn)。由于采用递归实现，需要考虑递归结束的条件。

算法性能

二分查找算法的时间复杂度为O(log n)，相对于串行查找的时间复杂度O(n)，效率有很大提升。但是，二分查找有以下几个限制：

1.数组必须是有序的，如果原数组无序，需要先排序。

2.只能对静态数组进行查找，不能对动态数组进行查找。

3.当数据量较小时，二分查找的执行效率不高，甚至不如直接循环查找。

4.对于插入和删除操作较多的情况，需要频繁对数组进行排序，导致时间复杂度较高。

总结

二分查找算法是一种基于二分思想的高效查找算法，对于有序数组的查找非常适用。常规实现和递归实现各有优劣，需要根据具体情况选择不同的实现方式。虽然二分查找算法具有一定的局限性，但是在实际应用中常常用于解决数据查找问题。