给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。并计算时间复杂度。（请先写出算法思想和实现步骤，再写代码）

这是一个常见的二分查找问题，也称为“搜索插入位置”。算法思想通常是利用已排序数组的特点，通过比较目标值与数组中间元素的大小关系来进行递归查找：

1. **算法思想**：
- 如果数组为空，说明目标值应该作为第一个元素插入，返回0。
- 找到数组中间元素，如果目标值等于中间元素，则直接返回它的索引。
- 如果目标值小于中间元素，我们在左半部分继续查找，因为目标值不可能出现在大于中间元素的地方。
- 否则，我们在右半部分查找，因为目标值不可能出现在小于中间元素的地方。
- 重复以上步骤，直到找到目标值或数组范围缩小到只剩下一个元素。

2. **实现步骤**：
- 初始化左右边界 `left` 和 `right`，初始时 `left = 0`, `right = len(arr) - 1`。
- 当 `left <= right` 时，执行循环：
- 计算中间索引 `mid`。
- 比较 `arr[mid]` 和目标值 `target` 的大小。
- 如果相等，返回 `mid`。
- 如果 `arr[mid] > target`，将 `right` 设置为 `mid - 1`，表示应在左半部分查找。
- 否则，将 `left` 设置为 `mid + 1`，表示应在右半部分查找。
- 循环结束后，如果没找到目标值，返回 `left`，即目标值应插入的位置。

3. **Python 代码示例**：

   def search_insert_sort(arr, target):
       left, right = 0, len(arr) - 1
       
       while left <= right:
           mid = (left + right) // 2
           if arr[mid] == target:
               return mid
           elif arr[mid] < target:
               left = mid + 1
           else:
               right = mid - 1
       
       return left

4. **时间复杂度分析**：
这种方法的时间复杂度为 O(log n)，其中 n 是数组长度，因为它是一个典型的二分查找过程。每一次循环都将搜索范围减半。当找不到目标值时，最多只需要进行 log_2(n) 次迭代。