二分查找的基本实现

关于二分查找法
二分查找法主要是解决在“一堆数中找出指定的数”这类问题。

而想要应用二分查找法，这“一堆数”必须有一下特征：

• 1，存储在数组中
• 2，有序排列

所以如果是用链表存储的，就无法在其上应用二分查找法了。

至于是顺序递增排列还是递减排列，数组中是否存在相同的元素都不要紧。不过一般情况，我们还是希望并假设数组是递增排列，数组中的元素互不相同。

二分查找的基本实现

int BinarySearch(int array[], int low, int high, int target)
{
    if (low > high || array[high]<target || array[low]>target) return 0;
    int mid;
    while (high >= low)
    {
        mid = (low + (high - low) / 2);
        if (array[mid] > target) high = mid - 1;
        else if (array[mid] < target) low = mid + 1;
        else //find the target
            return mid;
    }
    return 0;
}