Is it a pattern determine what index variable to be used in binary search?

Question

When doing https://leetcode.com/problems/search-insert-position. I found that it is hard to determine the combination of index variable.

For example, we have following combination in each level of the code.

(1)
l = 0 (stable)
r = len; r = len-1; (outbound / inbound)

(2)
loop(l < r); loop(l <= r) (outbound / inbound)

(3)
l = ind+1 (stable)
r = ind; r = ind-1 (include / exclude)

so now you have different combination of index variable, some of them are working, but if you change one of them, it will not pass all test cases

combo 1:
l=0, r=len (outbound); loop(l < r); l=ind+1, r=ind (include); work

combo 2:
l=0, r=len-1 (inbound); loop(l < r); l=ind+1, r=ind (include); !work

combo 3:
l=0, r=len (inbound); loop(l < r); l=ind+1, r=ind-1 (exclude); !work

combo 4:
l=0, r=len (outbound); loop(l < r); l=ind+1, r=ind (include); work

combo 5:
l=0, r=len-1 (inbound); loop(l<=r); l=ind+1, r=ind (include); work

comb 6:
l=0, r=len (outbound); recursive(l<=r); l=ind+1, r=ind (include); work

Below is the code I play around. Some of them are working and some of them are not working

// sm: l=0, r=len (outbound); loop(l < r); l=ind+1, r=ind (include); work
var searchInsert = function (ns, tar) {
  let l = 0;
  let r = ns.length; // outbound
  let ind;

  while (l < r) {
    ind = Math.floor((l + r) / 2);

    if (ns[ind] < tar) {
      l = ind + 1;
    } else if (ns[ind] > tar) {
      r = ind;
    } else {
      return ind; // existed
    }
  }

  return l; // insert
};

// sm: l=0, r=len-1 (inbound); loop(l < r); l=ind+1, r=ind (include); !work
var searchInsert = function (ns, tar) {
  let l = 0;
  let r = ns.length - 1; // inbound, cannot insert outbound
  let ind;

  while (l < r) {
    ind = Math.floor((l + r) / 2);

    if (ns[ind] < tar) {
      l = ind + 1;
    } else if (ns[ind] > tar) {
      r = ind;
    } else {
      return ind; // existed
    }
  }

  return l; // insert
};

// sm: l=0, r=len (inbound); loop(l < r); l=ind+1, r=ind-1 (exclude); !work
var searchInsert = function (ns, tar) {
  let l = 0;
  let r = ns.length;
  let ind;

  while (l < r) {
    ind = Math.floor((l + r) / 2);

    if (ns[ind] < tar) {
      l = ind + 1;
    } else if (ns[ind] > tar) {
      r = ind - 1;
    } else {
      return ind; // existed
    }
  }

  return l; // insert
};

// sm: l=0, r=len (outbound); loop(l < r); l=ind+1, r=ind (include); work
var searchInsert = function (ns, tar) {
  let l = 0;
  let r = ns.length;
  let ind;

  while (l < r) {
    ind = Math.floor((l + r) / 2);

    if (ns[ind] < tar) {
      l = ind + 1;
    } else if (ns[ind] > tar) {
      r = ind;
    } else {
      return ind; // existed
    }
  }

  return l; // insert
};

// sm: l=0, r=len-1 (inbound); loop(l<=r); l=ind+1, r=ind (include); work
var searchInsert = function (ns, tar) {
  let l = 0;
  let r = ns.length - 1;
  let ind;

  while (l <= r) {
    ind = Math.floor((l + r) / 2);

    if (ns[ind] < tar) {
      l = ind + 1;
    } else if (ns[ind] > tar) {
      r = ind - 1;
    } else {
      return ind; // existed
    }
  }

  return l; // insert
};

// sm: l=0, r=len (outbound); recurive(l<=r); l=ind+1, r=ind (include); work
var searchInsert = function (ns, tar) {
  let l = 0;
  let r = ns.length;
  return recur(ns, l, r, tar);
};

var recur = function (ns, l, r, tar) {
  if (l >= r) {
    return l;
  }

  const ind = Math.floor((l + r) / 2);

  if (ns[ind] === tar) {
    return ind;
  } else if (ns[ind] < tar) {
    return recur(ns, ind + 1, r, tar);
  } else if (ns[ind] > tar) {
    return recur(ns, l, ind, tar);
  }
};

const ns = [1, 3, 5, 6];
const tar = 5;
const out = searchInsert(ns, tar);
console.log(out);

My question is that, when you are presented a binary search question? How do you know which index combo you are going to use? Because it is really depend on the problem, trail and error

Answer 1

It is a very common question for people who just started learning binary search. I will try to analyze your examples case-by-case to see if you can understand better.

Rephrasing

It's helpful to rephrase the problem first. If we set ns[ns.length] to infinity, the problem is essentially asking you to find the first i such that ns[i] >= tar.

Idea

Consider the array [1, 3, 5, 6] and tar = 5, using the above definition on each element, we can see that the array can actually be evaluated to [F, F, T, T], so what we need to do is to just to find the index of the first T. The same can be applied to any arrays.

Implementation

Now here comes to the core of the problem. I will first illustrate why combo 2 and 3 do not work.

In combo 2, l=0, r=len-1 (inbound); loop(l < r); l=ind+1, r=ind (include);:
We can see that r is initilised to len - 1. However, what if the array given evaluates to [F, F, F, F]? The answer is 4 but r is initialized to 3, meaning that 4 will never be considered as an answer.

In combo 3, l=0, r=len (inbound); loop(l < r); l=ind+1, r=ind-1 (exclude);:
We can see that r=ind-1 if ns[ind] > tar. However, we want to find the first i such that ns[ind] >= tar so ns[ind] will still be a potential candidate! It is therefore incorrect to exclude it in this stage.

An example to consider is [3, 4, 5] and tar = 4. In the first iteration, ind = 1 and 4 gets eliminated immediately, which should be the correct answer.

You can verify that other combo works fine by seeing if your binary search will eliminate potential candidates wrongly.

Additional notes

As you have said, using which index combo really depends on the problem. However, in this particular problem, if I am asked to find the first i such that ns[i] >= tar, I would have a cleaner implementation as follows:

var searchInsert = function (ns, tar) {
  let l = 0;
  let r = ns.length;
  let ind;
  ns.push(Infinity);
  while (l < r) {
    ind = Math.floor((l + r) / 2);
    if (ns[ind] >= tar) {
      r = ind;
    } else {
      l = ind + 1;
    }
  }
  return r; // insert
};

which is just finding the first T in the array.