-1
$\begingroup$

I have seen several implementations of binary search where they can use either (left != right) or (left <= right). For example, in normal binary search where you check if target value is in the array, using inclusive right bound (right initially set to array size-1), you will use left <= right. When you want to find the first element larger or equal to target value, you use (left != right). I think my problem is I don't understand the difference between the two. Can someone tell me the intuition of when to pick one condition over the other?

$\endgroup$
1
  • 3
    $\begingroup$ cs.stackexchange is for questions about computer science, as in the academic discipline. As a rule of thumb, if your question depends on real-life languages/code/hardware/..., ask on Stack Overflow; if your question calls for abstract/mathematical models and reasoning, ask on Computer Science. $\endgroup$ Feb 29 '20 at 16:19
2
$\begingroup$

With the left != right condition, like in the following code sample, where vec is a sorted array and val is the value we are looking for,

int left = 0, right = (int)vec.size();
while(left != right) {
    int mid = (left + right) / 2;
    if (vec[mid] < val) left = mid + 1;
    else right = mid;
}

Both left and right will in the end denote the least index where vec[i] >= val (possibly outside the bounds of the array).

With the left <= right condition, like in the following code sample,

int left = 0, right = (int)vec.size() - 1;
while(left <= right) {
    int mid = (left + right) / 2;
    if (vec[mid] < val) left = mid + 1;
    else right = mid - 1;
}

left will in the end denote the least index where vec[i] >= val, and right the greatest index where vec[i] < val (either possibly outside the bounds of the array).

In my subjective opinion, the difference is so small that it is best to choose one and only ever use it. My preference is the former, as I find it easier to reason about just one value rather than two.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.