排序插入位置

Question

问题陈述：给定一个排序数组和一个目标值，return 如果找到目标则为索引。如果不是，return 按顺序插入时的索引。您可以假设数组中没有重复项。

这里有几个例子。

[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

我的代码:

public class Solution {
public int searchInsert(ArrayList<Integer> a, int b) {
    int low = 0, high = a.size()-1;
    int mid = (low+high)/2; 
    int retIndex = mid;
    while(low<=high){
        if(a.get(mid)<b){
            low = mid+1;
            mid = (low+high)/2;
            retIndex = low;
        }
        else{
            high = mid-1;
            mid = (low+high)/2;
            if(high<0) retIndex = 0;
            else retIndex = high;
        }
    }
    return retIndex;
}
}

但是这段代码有一些缺陷（return在一些 大输入 上少了或多了 1 个索引，放在这里是徒劳的），你可以直接检查 here，我无法弄清楚。谁能指出我的错误？或者这个问题的正确代码是什么？

编辑： 我正在展示它给出意外输出的精确输入。

A : [ 3, 4, 18, 19, 20, 27, 28, 31, 36, 42, 44, 71, 72, 75, 82, 86, 88, 97, 100, 103, 105, 107, 110, 116, 118, 119, 121, 122, 140, 141, 142, 155, 157, 166, 176, 184, 190, 199, 201, 210, 212, 220, 225, 234, 235, 236, 238, 244, 259, 265, 266, 280, 283, 285, 293, 299, 309, 312, 317, 335, 341, 352, 354, 360, 365, 368, 370, 379, 386, 391, 400, 405, 410, 414, 416, 428, 433, 437, 438, 445, 453, 457, 458, 472, 476, 480, 485, 489, 491, 493, 501, 502, 505, 510, 511, 520, 526, 535, 557, 574, 593, 595, 604, 605, 612, 629, 632, 633, 634, 642, 647, 653, 654, 656, 658, 686, 689, 690, 691, 709, 716, 717, 737, 738, 746, 759, 765, 775, 778, 783, 786, 787, 791, 797, 801, 806, 815, 820, 822, 823, 832, 839, 841, 847, 859, 873, 877, 880, 886, 904, 909, 911, 917, 919, 937, 946, 948, 951, 961, 971, 979, 980, 986, 993 ]
B : 902

此输入的预期 returned 值为：149
此输入的代码 returned 值为：148

Answer 1

对于最基本的测试用例，您的代码将失败：

[1,3,5,6], 5 → 2

你应该处理值在中间 a.get(mid) > b 和 a.get(mid)== b 的情况分别地。你也不需要单独维护一个变量retIndex。

因此将您的代码更改为：

    while(low<=high){
        if(a.get(mid)<b){
            low = mid+1;
            mid = (low+high)/2;                
        }
        else if(a.get(mid) > b){
            high = mid-1;
            mid = (low+high)/2;                
        }
        else return mid;
    }

    return low;//handles the case when no match is found.

Answer 2

您需要处理相等性并从更大的分支更改 return。

while(low<=high){
    if (a.get(mid) == b) return mid;
    else if(a.get(mid)<b){
        low = mid+1;
        mid = (low+high)/2;
        retIndex = low;
    }
    else {
        high = mid-1;
        retIndex = mid;
        mid = (low+high)/2;
    }
}

Answer 3

这个呢？

public class Solution {
public int searchInsert(ArrayList<Integer> a, int b) {
    int low = 0;
    int high = a.size();
    int candidateIdx = (low + high) / 2;
    int candidateValue;
    int prevCandidateIdx = -1;

    while (low != high ) {
        candidateValue = a.get(candidateIdx);
        if (candidateValue == b) {
            break;
        } else if (candidateValue < b && prevCandidateIdx == candidateIdx -1) {
            candidateIdx++;
            break;
        } else if (candidateValue < b) {
            low = candidateIdx;
        } else if (prevCandidateIdx == candidateIdx + 1) {
            break;
        } else {
            high = candidateIdx;
        }
        prevCandidateIdx = candidateIdx;
        candidateIdx = (low + high)/2;
    }
    return candidateIdx;
}
}

排序插入位置

Sorted insert position

java

algorithm

binary-search