java - Sorted insert position -

problem statement:given sorted array , target value, return index if target found. if not, return index if inserted in order. may assume no duplicates in array.

here few examples.

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

my code:

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

but there flaw in code (returning 1 less or more index on large inputs futile put here) can directly check here, unable figure out. can point out mistake? or correct code problem?

edit: presenting precise input giving unexpected output.

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 

the expected returned value input is: 149
code returned value input is: 148

your code fail basic test case:

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

you should handle case when value @ mid a.get(mid) > b , a.get(mid)== b separately. don't need separately maintain variable retindex.

so change code to:

    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 case when no match found. 

wiki