理解稍作修改的二分查找有困难吗?

huangapple go评论96阅读模式
英文:

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&lt;=last){
            int middle=(start+last)/2;
            
            if(target==nums[middle]){
                return middle;
            }
             else if(target&gt;nums[middle]){
            start=middle+1;
             }
            else
                last=middle-1;
            
        }
        return start; // this is the part i don&#39;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元素从未匹配过。所以你不断地将startlast越来越接近彼此。在最后一次迭代中,它们最终指向同一个元素。在这种情况下,start == middle == last

现在,它们都指向的元素要么大于target要么小于target

小于target

else if(target&gt;nums[middle]){
    start=middle+1;
}

在这个语句之后,lastmiddle仍然指向nums[middle],这个数字小于target。但start将指向它的下一个位置。nums[middle]之后的数字是第一个大于target的数字。如果你不明白为什么,请想想我们是如何从上一次迭代到达这种情况的。索引last总是指向一个大于target的数字,直到它多移动一位,这就是我们在这里看到的情况。

大于target

else
    last=middle-1;

在这种情况下,我们刚刚将last移动到了startmiddle以下的位置,我们知道它小于target。所以...当前位置是greaterlast指向的位置是less,然后当前位置(startmiddle仍然指向)是第一个大于target的数字。

无论哪种情况,start都会指向正确的位置 - 第一个大于target的元素的位置。

让我们在我们的示例数组中看看。当我们尝试插入150时,会发生什么?

  1. start为0(100),last为3(400)。通过整数除法,middle(0+3)/2,即1(200)。200 > 150,所以我们进入了else,将last设置为middle - 1,它是0(100)。
  2. 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&gt;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?

  1. 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 the else, and set last to middle - 1 and it's 0 (100).
  2. start is still 0 (100), but lastis now also 0 (100). They are equal, andmiddleis now also 0 (100). 100 &lt; 150, so we get to theelse 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

  1. 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 the else if and start is now middle +1, so 2 (300).
  2. start is 2 (300), last is 3 (400). middle is (2+3)/2 which is 2 (300). 300 < 350, so again we get to the else if and start is now middle + 1, so 3 (400).
  3. start is 3 (400), last is 3 (400) and middle will be the same. 400 > 350, so we get to the else, and last 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 < hilo <= 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 &lt; hi or lo &lt;= 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 &lt;= hi) {
            int mid = lo + (hi - lo) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            else if (nums[mid] &gt; 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.

huangapple
  • 本文由 发表于 2020年8月12日 00:37:33
  • 转载请务必保留本文链接:https://go.coder-hub.com/63362594.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定