java - 排序插入位置

标签 java algorithm binary-search

<分区>

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

这里有几个例子。

[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;
}
}

但此代码中存在一些缺陷(在某些大输入 上返回 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

此输入的预期返回值为:149
此输入的代码返回值为:148

最佳答案

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

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

你应该处理 mid a.get(mid) > ba.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.

关于java - 排序插入位置,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45831240/

相关文章:

python - Python中的二分搜索(二分法)

C 二分查找

java - Codahale 指标 : using @Timed metrics annotation in plain Java

c - 求解n个线性方程

algorithm - 伯罗斯惠勒变换 (BWT)

c - 算法每行中的计算/步骤数

python - 这种递归二分搜索算法可以更有效吗?

java - 日志: Queue's awaitRelease() has been interrupted abruptly while it wasn't released byte release() method

java - 线程 "main"org.apache.spark.sql.AnalysisException 中出现异常 : cannot resolve 'named_struct()' due to data type mismatch:

java - 为什么我们使用回调接口(interface)而不是仅仅传递对 Activity 的引用