二分查找演算法講解及其C++代碼實現

二分查找演算法是一種常用的查找演算法，也被稱為折半查找。它可以在有序的數組或列表中快速查找需要的元素。

演算法描述：

1. 首先確定數組的中間位置mid=(left+right)/2；
2. 然後將要查找的值key與中間位置的值進行比較；
3. 如果key等於中間位置的值，則查找成功，返回mid；
4. 如果key小於中間位置的值，則在左半部分繼續查找；
5. 如果key大於中間位置的值，則在右半部分繼續查找；
6. 重覆以上步驟，直到查找到key或者left>right時，查找結束。

C++代碼實現：

int binarySearch(int arr[], int n, int key)
{
    int left = 0;
    int right = n - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] > key)
            right = mid - 1;
        else if (arr[mid] < key)
            left = mid + 1;
    }
    return -1; // 查找失敗，返回-1
}

該函數接收三個參數，分別是：

1. arr：有序數組指針；
2. n：數組長度；
3. key：要查找的值。

如果查找成功，函數將返回該元素在數組中的下標；否則，返回-1表示查找失敗。

註意：使用二分查找演算法前，必須先對數組進行排序。