鉴于最近在网上看到的二分查找算法非常复杂，细节太多，不容易理解，下面给出几个实现简洁，又容易理解的代码模版。

首先，让我们记住最基本的二分查找模版：

在有序数组A中查找key，如果找到，返回位置索引，否则，返回-1;

int BinarySearch(int A[], int n, int key){    int left = 0, right = n - 1;    while (left <= right) {        int mid = left + (right - left) / 2;        if (A[mid] < key) {            left = mid + 1;        } else if (A[mid] > key) {            right = mid - 1;        } else {
   // A[mid] == key            return mid;        }    }    return -1;}

变种1：如果A有多个key元素，返回最大的，否则，返回-1

int BinarySearch(int A[], int n, int key){    int left = 0, right = n - 1;    int result = -1;    while (left <= right) {        int mid = left + (right - left) / 2;        if (A[mid] < key) {            left = mid + 1;        } else if (A[mid] > key) {            right = mid - 1;        } else {
   // A[mid] == key            result = mid;            left = mid + 1;//继续查找右半边        }    }    return result;}

变种2：如果A中有多个key元素，返回最小的，否则，返回-1

int BinarySearch(int A[], int n, int key){    int left = 0, right = n - 1;    int result = -1;    while (left <= right) {        int mid = left + (right - left) / 2;        if (A[mid] < key) {            left = mid + 1;        } else if (A[mid] > key) {            right = mid - 1;        } else {
   // A[mid] == key            result = mid;            right = mid - 1;// 继续查找左半边        }    }    return result;}

 变种3：在有序数组A中，查找出最小的比key大的元素索引。

int BinarySearch(int A[], int n, int key){　  if (A[n-1] < key)        return -1;    int left = 0, right = n - 1;    while (left ！= right) {        int mid = left + (right - left) / 2;        if (A[mid] <= key) {            left = mid + 1;        } else {            right = mid;        }     }    return left;}

 

变种4:在有序数组A中，查找出最大的比k小的元素索引。

int BinarySearch(int A[], int n, int key){    if (A[0] > key)        return -1;    int left = 0, right = n - 1;    while (left < right-1) {        int mid = left + (right - left) / 2;        if (A[mid] >= key) {            right = mid - 1;        } else {            left = mid;        }     }    if (A[right] < key) {        return right;    } else {        return left;    }}