C4.04 二分查找

课堂内容：二分查找

• 二分查找算法原理

二分查找也称折半查找，是一种在有序数组中查找某一特定元素的搜索算法。

• 二分查找_参考代码

int check(int nums[], int L, int R, int x)  
{
int mid;
    while (L <= R)  // 当左边界小于等于右边界时，继续查找
    {  
        mid = (L + R) / 2;  // 计算中间索引 
        if (nums[mid] == x)  // 如果中间元素等于 x，则返回其索引
            return mid;  
        else if (nums[mid] < x)  // 如果中间元素小于 x，则在右半部分继续查找
            L = mid + 1;  
        else  
            R = mid - 1;  // 如果中间元素大于 x，则在左半部分继续查找 
    }
    return -1;  // 如果循环结束仍未找到，则返回 -1
}

• x最靠左的位置_左边界

因为找的是数的左边界，所以需要在 mid 的值的左区间继续寻找 5 ，当 x == nums[mid] 时，用 ans = 将可能答案记录，在让 R = mid - 1即可，这样我们就可以继续在 mid 的左区间继续找 5 ，直到搜索范围为空。返回 ans。

• 左边界(记录法)_参考代码

int check(int nums[], int L, int R, int x)  
{
int mid，ans = -1;
    while (L <= R)  // 当左边界小于等于右边界时，继续查找
    {  
        mid = (L + R) / 2;  // 计算中间索引 
        if (nums[mid] == x)  // 如果中间元素等于 x
        {
            ans = mid; // 记录可能的答案
            R = mid - 1; // 因为是找左边界，则在左半部分继续查找 
        } 
        else if (nums[mid] > x) // 如果中间元素大于 x，则在左半部分继续查找 

            R = mid - 1;
        else  
            L = mid + 1; // 如果中间元素小于 x，则在右半部分继续查找
    }
    return ans;  // 如果循环结束仍未找到，则返回 ans
}

• 左边界(优化)_参考代码

因为找的是数的左边界，所以需要在 mid 的值的左区间继续寻找 5 ，只需在 nums[mid] >= x 时，让 R = mid(因为是 >= ，mid 可能是答案)。然后继续在 mid 及左区间继续找 5 。直到搜索范围为空，R 会停留在左边界就是答案。。

int check(int nums[], int L, int R, int x)  
{
int mid;
    while (L < R)  // 当左边界小于右边界时，继续查找
    {  
        mid = (L + R) / 2;  // 计算中间索引 
        if (nums[mid] >= x)  // 如果中间元素大于等于 x，则在左半部分继续查找
            R = mid; // 因为 mid 可能是答案 
        else // 如果中间元素小于 x，则在右半部分继续查找
            L = mid + 1;  
    }
    if(nums[R] == x) return ans; // 如果 R 停留位置等于 x，返回 R
    else return -1; // 否则返回 -1
}

• x最靠右的位置_右边界

因为找的是数的右边界，所以需要在 mid 的值的右区间继续寻找 5 ，只需在 nums[mid] <= x 时，让 L = mid(因为是 <= ，mid 可能是答案)。然后继续在 mid 及左区间继续找 5 。直到搜索范围为空，L 会停留在左边界就是答案。。

int check(int nums[], int L, int R, int x)  

{

int mid;

    while (L < R)  // 当左边界小于右边界时，继续查找

    {

        mid = (L + R + 1) / 2;  // 计算中间索引(需向上取整) 

        if (nums[mid] <= x)  // 如果中间元素小于等于 x，则在右半部分继续查找

            L = mid; // 因为 mid 可能是答案 

        else // 如果中间元素大 x，则在左半部分继续查找

            R = mid - 1;  

    }

    if(nums[L] == x) return L;  // 如果 L 停留位置等于 x，返回 L

    else return -1; //则返回 -1

}