# 4.1折半查找 

```C++
#include <cstdio>
#include <cstdlib>

typedef int ElementType;

int BinarySearch(const ElementType Array[], int Length, ElementType Key) {
    int low = 0;
    int high = Length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (Key < Array[mid]) {
            high = mid - 1;
        } else if (Key > Array[mid]) {
            low = mid + 1;
        } else {
            return mid;//found
        }
    }
    return -1;//not found
}
```