https://leetcode.com/problems/search-insert-position/
https://discuss.leetcode.com/topic/7874/my-8-line-java-solution
but I think if nums[mid] == target in the some early iteration, ur solution will be potentially wasting calculation cycles by not treating that as one of the cases, although more concise?
https://discuss.leetcode.com/topic/2661/simple-binary-search-solution
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.
http://www.bijishequ.com/detail/134759?p=66[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0
一直觉得Binary Search是非常好的考察正确性证明思路的一类题。因为它对区间……
下面就以这道题的原始Binary Search为例看一下为什么我们的代码是正确的，后面的题不会再这样繁琐的证明了。通过这道题了解思路和技巧，后面的题我们只要把握住关键点就可以了。
首先我们要搜索target的位置，所以用low和high组成的区间表示搜索范围，不变量Invariant就是：MustBe(low,high)表示target一定存在于区间[low,high]，否则它不存在于nums数组。接下来就是运用循环迭代不断缩小这个区间，最重要的是在这个过程中保持Invariant始终为真，最终我们得到的就一定是正确的结果：
- 初始化（Initialization）：初始时，MustBe(0,nums.length-1)包含了整个数组，按照MustBe的定义来说target要么存在于整个数组要么不存在，这肯定为真。于是Invariant初始状态没问题！
- 维护（Preservation）：对于这道题很容易，如果target在前一半，那么MustBe(low,mid-1)，所以更新high=mid-1就能维持Invariant为真了。反之，更新low=mid+1就行了。
- 终止（Termination）：能够清楚看出在循环过程中，low和high区间是在不断shrink。
有了以上三条，当循环终止时low > high并且MustBe(low,high)为真，于是我们就能知道target不存在。其实个人感觉：MustBe(low,high)应该叫做CanBe(low,high)更贴切，因为target可能不存在于数组中。所以最后CanBe(low,high)并且low > high，使得CanBe变成了MustNotBe。但也许CanBe语气比较弱，不像断言？后面我们会看到153-Find Minimum in Rotated Sorted Array找Minimum最小值，这道题的Invariant叫MustBe才比较合适！
1.3 循环终止前的样子
但这道题还没完，可以说最关键的一点来了：要返回插入位置而不是-1就完事了。这就要求我们仔细分析一下循环停止前那一刻是什么样子。因为low < high不可能直接跳到low > high，low = high - 1是倒数第二轮的情况，而最后一轮一定是low = high。于是就有low = mid = high，如果target > nums[mid]，那么会导致low = mid + 1，low就是插入位置。而如果target < nums[mid]，那么会导致high = mid - 1，low同样是插入位置。所以不断最后一轮是什么情况，low一定是插入位置！
1.4 解题关键点
这道题的代码非常标准，可以作为下面各道题Solution的模板。做下面各题时如果赶时间，比如面试时，可以先把上面的代码骨架写出来，再思考各个关键点。那Binary Search类型题都还有哪些变化，要把握住哪些关键点呢？在开始各个击破之前，先总结一下：
以二分查找为蓝本，这一类查找类型题还是能玩出不少变化的，例如最关键的几点有：
- low和high初始值：大部分都是数组的范围从0到N-1，个别像278-First Bad Version和374-Guess Number Higher or Lower是从1到N。
- 循环结束条件：
2.1 如果我们要找的target一定存在的话，那用low < high，最后low = high导致循环结束，low位置就是我们要找的数字了。这种一定存在的问题有：69-Sqrt、153-Find Minimum in Rotated Sorted Array、162-Find Peak Element、278-First Bad Version、374-Guess Number Higher or Lower。
2.2 如果target不一定存在的话，就要用low <= high，最终low大于high导致循环退出，说明target不存在。 - 区间缩减：
3.1 首先是如何确定缩减方向：最简单的是比较A[low/high]和A[mid]，复杂的如33-Search in Rotated Sorted Array还要比较是不是真的在那个区间内，还有就是367-Valid Perfect Square比较平方数的。
3.2 其次是如何确定缩减量。原则就是：确定搜索区间的缩减方向后，看如何更新low和high能保证Invariant为真。普通查找如35-Search Insert Position很简单，low=mid+1，high=mid-1。像278-First Bad Version中确定mid是Bad的话则high=mid，但mid不是Bad的话那么low=mid+1。69-Sqrt(x)中mid的平方小于x不代表mid一定小于x的平方根，例如2*2<5，所以low=mid，但反之mid一定大于x的平方根，所以high=mid+1。严重注意：high=mid没关系，但low=mid有可能导致死循环。因为low=high-1时low=mid，如果又进入low=mid分支相当于搜索区间没缩小。但high一定大于mid，所以不会造成死循环。方法就是：在low=high-1之前就跳出循环，然后自行判断。 - 最终结果确定：要看清题意最后需要返回什么，是-1，下标，还是值。
public int searchInsert(int[] A, int target) {
int low = 0, high = A.length-1;
while(low<=high){
int mid = (low+high)/2;
if(A[mid] == target) return mid; // not work if there is duplicate
else if(A[mid] > target) high = mid-1;
else low = mid+1;
}
return low;
}but I think if nums[mid] == target in the some early iteration, ur solution will be potentially wasting calculation cycles by not treating that as one of the cases, although more concise?
public int searchInsert(int[] nums, int target) {
int low = 0, high = nums.length;
while(low < high) {
int mid = low + (high - low) / 2;
if(nums[mid] < target)
low = mid + 1;
else
high = mid;
}
return low;
}
This could be the most concise solution. And the point is: it also handle duplicate!
public int searchInsert(int[] nums, int target) {
return firstOccurrenceRecur(nums,target,0,nums.length-1);
}
public int firstOccurrenceRecur(int[] nums, int target, int low, int high) {
if (low > high) { return low; }
int mid = low + ( (high - low) >> 1 );
if (nums[mid] < target) {
return firstOccurrenceRecur(nums,target,mid + 1,high);
} else {
return firstOccurrenceRecur(nums,target,low,mid-1);
}
}https://discuss.leetcode.com/topic/2661/simple-binary-search-solution
Only two cases:
1 if found, just return current index
2 if not found, return next index where the search end
1 if found, just return current index
2 if not found, return next index where the search end
int search(int A[], int start, int end, int target) {
if (start > end) return start;
int mid = (start + end) / 2;
if (A[mid] == target) return mid;
else if (A[mid] > target) return search(A, start, mid - 1, target);
else return search(A, mid + 1, end, target);
}
int searchInsert(int A[], int n, int target) {
return search(A, 0, n - 1, target);
}