1.这道题的解法并不难找到难的是要求时间复杂度为O(logn)。对于这个要求因为题目给定的数组为无重复元素的升序数组第一时间想到的是使用二分法通过不断夹逼找到target所对应的索引index。最开始的思路是不断的将index进行二分判断该索引对应的数组元素大小如果正好相等就直接返回索引如果大于target就将index向右二分小于target就将index向左二分。可能会出现数组中没有与target相等值的情况于是定义一个last_val变量保存上一次的数组元素值如果上次的大小关系与本次的正好相反比如上次是大于这次是小于那么就找到了应该插入的索引位置初步写出的代码如下1. int searchInsert(int* nums, int numsSize, int target) { 2. int index numsSize / 2; 3. int last_val nums[index]; 4. while (index 0 index numsSize){ 5. if (nums[index] target){ 6. return index; 7. } 8. if (nums[index] target){ 9. if (last_val target){ 10. return index 1; 11. } 12. last_val nums[index]; 13. index (index numsSize) / 2; 14. } 15. if (nums[index] target){ 16. if (last_val target){ 17. return index - 1; 18. } 19. last_val nums[index]; 20. index / 2; 21. } 22. } 23. return index; 24. }2.程序超时了。询问ai后总结出如下几点问题由于”/”只取整除部分的值可能会出现index永远不再发生变化的情况之前是3数组长度是4(34)/23索引将永远是3。区间更新错误真正的二分法应该是不断缩小搜索区间而我初步写出的代码区间并没有减小。循环条件while (index 0 index numsSize)没有明确的区间收敛逻辑。3.正确的做法应该是使用左右双指针来进行二分代码如下1. int searchInsert(int* nums, int numsSize, int target) { 2. // 1. 初始化闭区间 [left, right]覆盖整个数组 3. // left区间左边界初始为第一个元素索引 4. // right区间右边界初始为最后一个元素索引 5. int left 0, right numsSize - 1; 6. 7. // 2. 循环条件left right闭区间的核心只要区间有元素就继续 8. while (left right){ 9. // 3. 计算中点mid 10. // 等价写法int mid (left right) / 2; 11. // 更安全写法int mid left (right - left) / 2;避免溢出 12. int mid (left right) / 2; 13. 14. // 4. 找到目标值直接返回mid题目要求的索引 15. if (nums[mid] target){ 16. return mid; 17. } 18. 19. // 5. 目标值比mid大去右半区间搜索 20. // 收缩左边界left mid 1mid已经判断过排除 21. if (nums[mid] target){ 22. left mid 1; 23. } 24. 25. // 6. 目标值比mid小去左半区间搜索 26. // 收缩右边界right mid - 1mid已经判断过排除 27. if (nums[mid] target){ 28. right mid - 1; 29. } 30. } 31. 32. // 7. 循环结束left rightleft就是插入位置 33. return left; 34. }二分法通过左右双指针来不断缩小区间范围循环条件left right就是二分法的核心。4.返回值的详解如果找到目标值了就直接返回目前的mid。如果二分到了最后left一定等于mid。如果二分到最后发现最后一个mid索引对应的数组元素值仍小于target说明应该插入到该索引右边此时if里leftmid1返回left刚好。如果二分到最后发现最后一个mid索引对应的数组元素值仍大于target说明应该插入到该索引左边此时left等于mid返回left刚好。