023/2023-09-20
# 2023-09-20
一、问题背景
1. 1.1 题目描述
在给定一个整数数组（已排序），以及一个目标值，查找目标值第一次出现的位置。如果目标值不存在于数组中，则返回 -1。
1. 1.2 输入输出格式
输入格式：
• 第一行包含一个整数 n 表示数组长度。
• 第二行包含 n 个整数，表示排序后的数组。
• 第三行包含一个整数 target 表示目标值。
输出格式：
• 输出一个整数，表示目标值第一次出现的位置，如果目标值不存在，则输出 -1。
1. 1.3 示例
输入：
``````5
1 2 4 5 6
3``````
输出：
``````-1
``````
1. 1.4 备注
- 数组长度 n 满足 0 ≤ n ≤ 100000。
- 整数范围满足 -100000 ≤ target ≤ 100000。
二、解题思路
1. 2.1 方法一：暴力搜索
1. 2.1.1 算法描述
暴力搜索法的基本思路是遍历数组，从左至右依次检查每个元素，检查目标值是否等于当前元素。如果找到目标值，记录下该位置，并停止搜索；如果遍历完整个数组都没有找到目标值，则返回 -1。
1. 2.1.2 代码实现
```python
def first_occurrence(nums, target):
n = len(nums)
for i in range(n):
if nums[i] == target:
return i
return -1
```
1. 2.2 方法二：二分查找
1. 2.2.1 算法描述
二分查找法利用了数组已排序的特性，通过不断缩小查找范围来高效地定位目标值。首先找到数组的中间元素，比较中间元素和目标值，根据目标值的位置选择继续在左半部分或右半部分进行查找。重复上述过程，直到目标值被找到或查找范围缩小到无法继续查找时结束。
1. 2.2.2 代码实现
```python
def binary_search(nums, target):
n = len(nums)
left, right = 0, n - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
if mid == 0 or nums[mid - 1] != target:
return mid
else:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
1. 2.3 方法三：双指针
1. 2.3.1 算法描述
双指针法通过将数组分为左右两部分，分别在左右两端进行搜索。初始化时，左指针指向数组开头，右指针指向数组末尾。根据目标值与当前左右端元素的关系，移动左指针或右指针来缩小查找范围，最终找到目标值第一次出现的位置。
1. 2.3.2 代码实现
```python
def two_pointers(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
if mid == 0 or nums[mid - 1] != target:
return mid
else:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
三、复杂度分析
1. 3.1 方法一：暴力搜索
- 时间复杂度：O(n)，其中 n 是数组长度。
- 空间复杂度：O(1)。
1. 3.2 方法二：二分查找
- 时间复杂度：O(log n)，其中 n 是数组长度。
- 空间复杂度：O(1)。
1. 3.3 方法三：双指针
- 时间复杂度：O(log n)，其中 n 是数组长度。
- 空间复杂度：O(1)。
四、总结
通过上述三种方法的分析，我们可以看出，二分查找法在处理有序数组时具有较高的效率，时间复杂度为 O(log n)。此外，双指针法也是一种有效的方法，其时间复杂度同样为 O(log n)。在实际应用中，可以根据具体需求选择合适的方法。对于本题而言，二分查找法是最优的选择。
五、代码实现
```python
class Solution:
def searchInsert(self, nums, target):
# 方法一：暴力搜索
# return self.bubble_sort(nums, target)
# 方法二：二分查找
# return self.binary_search(nums, target)
# 方法三：双指针
return self.two_pointers(nums, target)
def bubble_sort(self, nums, target):
n = len(nums)
for i in range(n):
for j in range(n - i - 1):