问一个关于二分法的简单有关问题，何时该 return left;何时该 return right，多谢！
问一个关于二分法的简单问题，何时该 return left;何时该 return right，谢谢！！！
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
问题在注视处 谢谢
------解决方案--------------------
lz 你注释的那个地方，其实是属于没有找到的情况下的返回，你left、right 都没什么意义
但是参照你给的例子，
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
这3个例子表示的意思显然是希望，要求你找一个数X，当X在没找到的情况下，返回如果插入这个数，这个数应该在哪个下标上（ If not, return the index where it would be if it were inserted in order.），相当于返回比X大的数当中最小的那个数的下标，因为如果新插入这个数X，这个数应该排在比X大的数当中最小的那个数的下标上，其余数字依次后移一个下标的位置。
mid是你当前这一轮查找的数的下标，当没找到的情况下，比mid大的数当中最小的那个数的下标就是mid+1
而right = mid - 1; left = mid + 1; 所以返回left
同理反过来， 如果题目要求你在没找到的情况下，返回比X小的数当中最大的那个数的下标，则返回right
class Solution {
public:
int searchInsert(int A[], int n, int target) {
if(NULL == A || 0 == n)
return 0;
int left = 0, right = n-1, mid = 0;
while(left <= right)
{
mid = (right+left)/2;
if(target == A[mid])
return mid;
else if(target < A[mid])
right = mid - 1;
else
left = mid + 1;
}
return left; //我实际试了几个数，明白必须要 return left;而不能 return right，但理解的不是特别深刻，何时该 return left;何时该 return right，是说所有的二分法的题目都要试数，还是说一般都return left;？ 谢谢
}
};
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
问题在注视处 谢谢
------解决方案--------------------
lz 你注释的那个地方，其实是属于没有找到的情况下的返回，你left、right 都没什么意义
但是参照你给的例子，
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
这3个例子表示的意思显然是希望，要求你找一个数X，当X在没找到的情况下，返回如果插入这个数，这个数应该在哪个下标上（ If not, return the index where it would be if it were inserted in order.），相当于返回比X大的数当中最小的那个数的下标，因为如果新插入这个数X，这个数应该排在比X大的数当中最小的那个数的下标上，其余数字依次后移一个下标的位置。
mid是你当前这一轮查找的数的下标，当没找到的情况下，比mid大的数当中最小的那个数的下标就是mid+1
而right = mid - 1; left = mid + 1; 所以返回left
同理反过来， 如果题目要求你在没找到的情况下，返回比X小的数当中最大的那个数的下标，则返回right