35. 搜索插入位置
#leetcode#二分查找 2025-01-31

Problem: 35. 搜索插入位置

解析

二分查找的简单应用

二分查找 递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//! log(n),log(n)->二分查找log(n)次，函数递归栈log(n)大小
class Solution {
 public:
  int searchInsert(vector<int> &nums, int target) {
    return binarySearch(nums, 0, nums.size() - 1, target);
  }
  int binarySearch(vector<int> nums, int left, int right, int target) {
    if (left > right) {
      return left;
    }
    int mid = (left + right) / 2;
    if (nums[mid] == target) {
      return mid;
    } else if (nums[mid] > target) {
      return binarySearch(nums, left, mid - 1, target);
    } else {
      return binarySearch(nums, mid + 1, right, target);
    }
  }
};

二分查找 迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//! log(n),1->二分查找log(n)次，常数空间
class Solution {
 public:
  int searchInsert(vector<int> &nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (nums[mid] < target) {
        left = mid + 1;
      } else if (nums[mid] > target) {
        right = mid - 1;
      } else {
        return mid;
      }
    }
    return left;
  }
};