LeetCode 二分查找、移除元素与有序数组平方题解

LeetCode 704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

必须编写一个具有 O(log n) 时间复杂度的算法。

解题思路

在数组的第一个位置和最后一个位置分别设置 low 指针和 high 指针，在数组的中间位置设置 mid 指针。

• 若 mid 所指元素小于 target，将 low 移动到 mid 右侧第一个位置。
• 若 mid 所指元素大于 target，将 high 移动到 mid 左侧第一个位置。
• 若 mid 等于 target，返回下标。
• 若遍历结束未找到，返回 -1。

参考代码

int search(int* nums, int numsSize, int target) {
    int low = 0, high = numsSize - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) low = mid + 1;
        else if (nums[mid] > target) high = mid - 1;
    }
    return -1;
}

二分查找法只适用于有序数组。需注意区间边界，分为左闭右闭 [low, high] 和左闭右开 [low, high)。

第一种写法：左闭右闭

• while (left <= right)：left == right 有意义。
• right = middle - 1：当前 middle 不是 target，左区间结束下标为 middle - 1。

第二种写法：左闭右开

• while (left < right)：left == right 无意义。
• right = middle：下一个查询区间不会去比较 nums[middle]。

int search(int* nums, int numsSize,  target) {
     low = , high = numsSize;
     (low < high) {
         mid = (low + high) / ;
         (nums[mid] < target) low = mid + ;
          (nums[mid] > target) high = mid;
          mid;
    }
     ;
}