英文:
Trouble understanding slightly modified binary search?
问题
Sure, here's the translated code for you:
class Solution {
public int searchInsert(int[] nums, int target) {
int start = 0;
int last = nums.length - 1;
while (start <= last) {
int middle = (start + last) / 2;
if (target == nums[middle]) {
return middle;
} else if (target > nums[middle]) {
start = middle + 1;
} else {
last = middle - 1;
}
}
return start; // 这部分我不理解。为什么我要返回 start?
}
}
Please note that I've only translated the code as per your request, without providing additional content.
英文:
Hi guys i am trying to solve a problem on leetcode called "search insert position". Heres the problem:
<https://leetcode.com/problems/search-insert-position/>
Problem statement:
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.
It's a simple binary search, the only part i don't understand is that i have to return the lower bound at the end to get the correct answer. I don't understand why. if anyone can explain me, i would appreciate it.
class Solution {
public int searchInsert(int[] nums, int target) {
int start=0;
int last= nums.length-1;
while(start<=last){
int middle=(start+last)/2;
if(target==nums[middle]){
return middle;
}
else if(target>nums[middle]){
start=middle+1;
}
else
last=middle-1;
}
return start; // this is the part i don't understand. why do i have to return start?
}
}
答案1
得分: 1
理解了这一点,你必须注意到这个练习的第二个要求:返回应该插入元素的位置。
假设你想要将数字150插入以下表格中。
╔═════╦═════╦═════╦═════╗
║ 100 ║ 200 ║ 300 ║ 400 ║
╠═════╬═════╬═════╬═════╣
║ 0 ║ 1 ║ 2 ║ 3 ║
╚═════╩═════╩═════╩═════╝
这是通过创建一个更大的数组来完成的,将所有在150之前的元素复制到它们原来的位置,然后添加数字150,然后将所有在150之后的数字复制到它们原来的位置索引加一的地方。
╔═════╦═════╦═════╦═════╦═════╗
║ ║ ║ ║ ║ ║
╠═════╬═════╬═════╬═════╬═════╣
║ 0 ║ 1 ║ 2 ║ 3 ║ 4 ║
╚═════╩═════╩═════╩═════╩═════╝
╔═════╦═════╦═════╦═════╦═════╗
║ 100 ║ ║ ║ ║ ║
╠═════╬═════╬═════╬═════╬═════╣
║ 0 ║ 1 ║ 2 ║ 3 ║ 4 ║
╚═════╩═════╩═════╩═════╩═════╝
╔═════╦═════╦═════╦═════╦═════╗
║ 100 ║ 150 ║ ║ ║ ║
╠═════╬═════╬═════╬═════╬═════╣
║ 0 ║ 1 ║ 2 ║ 3 ║ 4 ║
╚═════╩═════╩═════╩═════╩═════╝
╔═════╦══════╦═════╦═════╦═════╗
║ 100 ║ 150 ║ 200 ║ 300 ║ 400 ║
╠═════╬══════╬═════╬═════╬═════╣
║ 0 ║ 1 ║ 2 ║ 3 ║ 4 ║
╚═════╩══════╩═════╩═════╩═════╝
现在你知道这是如何完成的,你知道插入所需的索引是第一个大于你的target
的数字的索引。如果所有的数字都大于你的target
,那么这意味着0(所有现有数字都将被移动到1到N的位置),如果所有的数字都小于你的target
,那么这将是数字N - 现有数组的长度(它不是现有数组的合法索引,但正如我解释的,如果你真的想插入这个数字,你必须创建一个新的数组。但这不是这个练习的一部分)。
现在,为什么start
是正确的索引呢?
当你要查找的元素不在数组中时,middle
元素从未匹配过。所以你不断地将start
和last
越来越接近彼此。在最后一次迭代中,它们最终指向同一个元素。在这种情况下,start == middle == last
。
现在,它们都指向的元素要么大于target
要么小于target
。
小于target
else if(target>nums[middle]){
start=middle+1;
}
在这个语句之后,last
和middle
仍然指向nums[middle]
,这个数字小于target
。但start
将指向它的下一个位置。nums[middle]
之后的数字是第一个大于target
的数字。如果你不明白为什么,请想想我们是如何从上一次迭代到达这种情况的。索引last
总是指向一个大于target
的数字,直到它多移动一位,这就是我们在这里看到的情况。
大于target
else
last=middle-1;
在这种情况下,我们刚刚将last
移动到了start
和middle
以下的位置,我们知道它小于target。所以...当前位置是greater,last
指向的位置是less,然后当前位置(start
和middle
仍然指向)是第一个大于target
的数字。
无论哪种情况,start
都会指向正确的位置 - 第一个大于target
的元素的位置。
让我们在我们的示例数组中看看。当我们尝试插入150时,会发生什么?
start
为0(100),last
为3(400)。通过整数除法,middle
为(0+3)/2
,即1(200)。200 > 150,所以我们进入了else
,将last
设置为middle - 1
,它是0(100)。start
仍然为0(100),但last
现在也是0(100)。它们相等,middle
现在也是0(100)。100
英文:
To understand that, you must notice the second requirement of the exercise: returning the position where the element should be inserted.
Suppose you want to insert the number 150 in the following table.
╔═════╦═════╦═════╦═════╗
║ 100 ║ 200 ║ 300 ║ 400 ║
╠═════╬═════╬═════╬═════╣
║ 0 ║ 1 ║ 2 ║ 3 ║
╚═════╩═════╩═════╩═════╝
The way this is done is creating a larger array, copying all the elements that come before 150 in the same position that they are, then adding the number 150, then copying all the numbers that come after 150 with one index higher than they were.
╔═════╦═════╦═════╦═════╦═════╗
║ ║ ║ ║ ║ ║
╠═════╬═════╬═════╬═════╬═════╣
║ 0 ║ 1 ║ 2 ║ 3 ║ 4 ║
╚═════╩═════╩═════╩═════╩═════╝
╔═════╦═════╦═════╦═════╦═════╗
║ 100 ║ ║ ║ ║ ║
╠═════╬═════╬═════╬═════╬═════╣
║ 0 ║ 1 ║ 2 ║ 3 ║ 4 ║
╚═════╩═════╩═════╩═════╩═════╝
╔═════╦═════╦═════╦═════╦═════╗
║ 100 ║ 150 ║ ║ ║ ║
╠═════╬═════╬═════╬═════╬═════╣
║ 0 ║ 1 ║ 2 ║ 3 ║ 4 ║
╚═════╩═════╩═════╩═════╩═════╝
╔═════╦══════╦═════╦═════╦═════╗
║ 100 ║ 150 ║ 200 ║ 300 ║ 400 ║
╠═════╬══════╬═════╬═════╬═════╣
║ 0 ║ 1 ║ 2 ║ 3 ║ 4 ║
╚═════╩══════╩═════╩═════╩═════╝
Now that you know how this works, you know that the index you need for insertion is the one of the first number that is greater than your target
. If all numbers are greater than your target
, this means 0 (and all the existing numbers will be shifted to places 1 through N), and if all numbers are less than your target
, this will be the number N - the length of the existing array (it's not a legal index in the existing array, but as I explained, if you really wanted to insert the number, you'd have to create a new array. But that's not part of this exercise).
Now, why is start
the correct index?
When the element you are looking for is not in the array, the middle
element is never matching. So you keep moving the start
and last
closer and closer to each other. In the last iteration, you end up with them pointing to the same element. In this case, start == middle == last
.
Now, the element that they are both pointing to is either greater than target
or less than target
.
Less than target
else if(target>nums[middle]){
start=middle+1;
}
After this statement, we have last
and middle
still pointing to the nums[middle]
number which is less than target
. But start
is going to point one position after it. The number after nums[middle]
is the first number that is greater than target
. If you don't understand why, think how we got to this situation from the previous iteration. The index last
always points to a number that is greater than target
, until it is moved one position "too much", which is what we see here.
Greater than target
else
last=middle-1;
In this case, we have just moved last
to a position that is below start
and middle
- which we know is less than *target. So... the current position is *greater*, the position where
last point is *less
, then the current position (which start
and middle
are still pointing to) is the first number that is greater than target
.
In both cases, start
will be pointing to the correct position - that of the first element that is greater than target
.
Let's see it in our example array. When we try to insert 150, what happens?
start
is 0 (100),last
is 3 (400).middle
, by integer division, is(0+3)/2
which is 1 (200). 200 > 150, so we get to theelse
, and setlast
tomiddle - 1
and it's 0 (100).start is still 0 (100), but
lastis now also 0 (100). They are equal, and
middleis now also 0 (100). 100 < 150, so we get to the
else if, and
start` is now set to 1 (200).
So as soon as start
has moved to a number that is greater than target
, we stopped, and indeed, the point of insertion should be 1!
Let's do the same with 350
start
is 0 (100),last
is 3 (400).middle
, by integer division, is(0+3)/2
which is 1 (200). 200 < 350, so we get to theelse if
andstart
is nowmiddle +1
, so 2 (300).start
is 2 (300),last
is 3 (400).middle
is(2+3)/2
which is 2 (300). 300 < 350, so again we get to theelse if
andstart
is nowmiddle + 1
, so 3 (400).start
is 3 (400),last
is 3 (400) and middle will be the same. 400 > 350, so we get to theelse
, andlast
will move to 2 (300).
Now that start
is greater than last
, we see, again, that start
is in fact the first element that is greater than 350. Indeed, the correct insert point for 350 would be 3.
答案2
得分: 0
根据数组的大小或其分区(偶数或奇数)或我们设计二分搜索算法的方式,有时低和高之间会有一个索引差异(基于停止条件,可以是lo < hi
或lo <= hi
,例如)。真正重要的是返回哪一个,我们只需调整这个差异。
在这个问题中,lo
将返回预期的内容:
public final class Solution {
public static final int searchInsert(int[] nums, int target) {
int lo = 0;
int hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] > target) {
hi = mid - 1;
}
else {
lo = mid + 1;
}
}
return lo;
}
}
英文:
Depending on size of the array or its partitions (even or odd), or the way we'd design a Binary Search algorithm, sometimes there'd be one index difference between low and high (based on the stopping criterion which could be lo < hi
or lo <= hi
for instance). It does not really matter which one to return, we have to just adjust for that difference.
In this question lo
would return what's expected:
public final class Solution {
public static final int searchInsert(int[] nums, int target) {
int lo = 0;
int hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] > target) {
hi = mid - 1;
}
else {
lo = mid + 1;
}
}
return lo;
}
}
答案3
得分: 0
在找到中点之前,我们需要初始化起始点。每次都会检查是否找到目标元素,如果没有找到目标元素,就会更新起始点。
英文:
before finding the midpoint we need to initialize the starting point. Every time it checks whether the target element is found or not, if it didn't found the target element then updates the starting point.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论