public int BS(int a){ int first = 0; int last = q.length-1; int point = q.length/2; if (q.length != 0 && a >= q[0] && a <= q[q.length-1]){ while (a != q[point]){ if (q[first]==q[last]){ return -1; } else if (a > q[point]){ first = point+1; point = (first + last)/2; } else { last = point; point = (first + last)/2; } } return point; } else { return -1; }

I would like to know the opinion of professionals: is a binary search really implemented, are there no working conditions, is there room for maneuver in the direction of optimization without killing the "originality"

  • Some he is not very classic. Here it is necessary to think. Especially about whether it can get stuck and whether first and last turn over. The presence of a shift in one branch and the absence of another look like a crutch. Adjusts q[first]==q[last] and there is no point in smearing the assignment of a point in three places - it is logical to make it the first in the loop. - Qwertiy ♦

1 answer 1

At least your algorithm contains a classical error for most binary search implementations - the addition of the left and right indexes can exceed Integer.MAX_VALUE and give a negative value.

But in general, will work.

 public int BS(int a){ int first = 0; int last = q.length-1; int point = q.length/2; if (q.length != 0 && a >= q[0] && a <= q[q.length-1]){ while (a != q[point]){ if (q[first]==q[last]){ return -1; } else if (a > q[point]){ first = point+1; point = (first + last)/2; // возможно переполнение int } else { last = point; // !!! point = (first + last)/2; // возможно переполнение int } } return point; } else { return -1; }