题目描述（简单难度）

给定一个有序数组，依旧是二分查找，不同之处是如果没有找到指定数字，需要返回这个数字应该插入的位置。 这道题比较简单，在二分查找的基础上，只要想清楚返回啥就够了。想的话，就考虑最简单的情况如果数组只剩下 2 5，target 是 1, 3, 6 的时候，此时我们应该返回什么就行。 1. public int searchInsert(int[] nums, int target) { 2. int start = 0; 3. int end = nums.length - 1; 4. if (nums.length == 0) { 5. return 0; 6. } 7. while (start < end) { 8. int mid = (start + end) / 2; 9. if (target == nums[mid]) { 10. return mid; 11. } else if (target < nums[mid]) { 12. end = mid; 13. } else { 14. start = mid + 1; 15. } 16. } 17. //目标值在不在当前停的位置的前边还是后边 18. if(target>nums[start]){ 19. return start + 1; 20. } 21. //如果小于的话，就返回当前位置，跑步超过第二名还是第二名，所以不用减 1。 22. else{ 23. return start; 24. } 25. }

时间复杂度：O（log（n））。 空间复杂度：O（1）。 这道题不难，但是对于二分查找又有了一些新认识。 首先，一定要注意，数组剩下偶数个元素的时候，中点取的是左端点。例如 1 2 3 4，中点取的是 2。正因为如此，我们更新 start 的时候不是直接取 mid ，而是 mid + 1。因为剩下两个元素的时候，mid 和 start 是相同的，如果不进行加 1 会陷入死循环。 然后上边的算法，返回最终值的时候，我们进行了一个 if 的判断，那么能不能避免呢。 * 第一种思路，参考这里。 首先为了让 start 在循环的时候多加 1，我们将循环的 start < end 改为 start <= end。 这样就会出现一个问题，当 start == end，此时 mid 不仅等于了 start 还会等于 end，所以之前更新 end 是直接赋 mid，现在需要改成 end = mid - 1，防止死循环。这样就达到了目标。 1. public int searchInsert(int[] nums, int target) { 2. int start = 0; 3. int end = nums.length - 1; 4. if (nums.length == 0) { 5. return 0; 6. } 7. while (start <= end) { 8. int mid = (start + end) / 2; 9. if (target == nums[mid]) { 10. return mid; 11. } else if (target < nums[mid]) { 12. end = mid - 1; 13. } else { 14. start = mid + 1; 15. } 16. } 17. 18. return start; 19. 20. }

• 第二种思路，参考这里。 我们开始更新 start 的时候，是 mid + 1，如果剩两个元素，例如 2 4，target = 6 的话，此时 mid = 0，start = mid + 1 = 1，我们返回 start + 1 = 2。如果 mid 是右端点，那么 mid = 1，start = mid + 1 = 2，这样就可以直接返回 start 了，不需要在返回的时候加 1 了。 怎么做到呢？最最开始的时候我们取 end 的时候是 end = nums.length - 1。如果我们改成 end = nums.length，这样每次取元素的时候，如果和之前对比，取到的就是右端点了。这样的话，最后返回的时候就不需要多加 1 了。 1. public int searchInsert(int[] nums, int target) { 2. int start = 0; 3. int end = nums.length; 4. if (nums.length == 0) { 5. return 0; 6. } 7. while (start < end) { 8. int mid = (start + end) / 2; 9. if (target == nums[mid]) { 10. return mid; 11. } else if (target < nums[mid]) { 12. end = mid; 13. } else { 14. start = mid + 1; 15. } 16. } 17. 18. return start; 19. 20. }

总

虽然题很简单，但对二分查找有了更多的理解。 添加好友一起进步~ 如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^ 如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情