首页 > 代码库 > Search Insert Position 查找给定元素在数组中的位置，若没有则返回应该在的位置
Search Insert Position 查找给定元素在数组中的位置，若没有则返回应该在的位置
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0
如题所述，最直观的做法就是二分查找。不过在使用二分查找解决此问题时，需要多加小心，先考虑清楚所有情况，再开始编码。
首先考虑边界：
- 若给定target小于数组第一个元素，返回0；
- 若target大于最后一个元素，返回n
使用二分，结束循环条件应该是high-low=1的情况。
例如[1,3,5,6]中查找2，二分一次后，low=0,high=1，此时A[low]=1,A[high]=3。
若按照平常使用的二分查找就应该找不到元素exit了，但是要返回元素的值则需要再进一步处理，此时low+1，或high-1即为元素应该的位置。
下面代码里我把target等于边界值（数组第1个和第n个）的情况放到最后比较了。
1 class Solution { 2 public: 3 int searchInsert(int A[], int n, int target) { 4 if(A == NULL || n < 1) 5 return -1; 6 if(target < A[0]) 7 return 0; 8 if(target > A[n-1]) 9 return n;10 11 int low = 0;12 int high = n-1;13 14 int mid = 0;15 16 while(high-low>1){17 mid = low + (high - low)/2;18 if(A[mid] == target)19 return mid;20 else if(A[mid] > target)21 high = mid;22 else23 low = mid;24 }25 26 if(high-low ==1)27 if(A[low] == target)28 return low;29 if(A[high] == target)30 return high;31 else32 return low+1;33 34 }35 };
Search Insert Position 查找给定元素在数组中的位置，若没有则返回应该在的位置
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。