Variants of binary search in Javascript
qwerty
73
  1. Contains Key, Return True or False
  2. Contains Key, Return Index of first occurrence of a key
  3. No Key, Return Index of last occurrence of a key
  4. No Key, Return Index of least element greater than key
  5. No Key, Return Index of greatest element less than key
// a is arr, key is target, low = 0, hi = a.length-1
// mid = low + (high - low) / 2 to avoid integer overflow

let contains = (a, key, low, high, ans = false) =>  { // return true/false
    while (low <= high) {
        let mid = low + (high - low) / 2;
        if (a[mid] < key) low = mid + 1; 
        else if (a[mid] > key) high = mid - 1; 
        else if (a[mid] == key) { 
             ans = true;break; 
        }
    }
    return ans;
}
let containsfirst = (a, key, low, high, ans = -1) => { // return first occurence of key
    while (low <= high) {
        let mid = low + (high - low + 1) / 2;
        if (a[mid] < key) low = mid + 1;
        else if (a[mid] > key) high = mid - 1;
        else if (a[mid] == key) {
            ans = mid;
            high = mid - 1;
        }
    }
    return ans;
}
let containslast = (a, key, low, high, ans = -1) => { // return last occurence of key
    while (low <= high) {
        let mid = low + (high - low + 1) / 2;
        if (a[mid] < key) low = mid + 1;
        else if (a[mid] > key) high = mid - 1;
        else if (a[mid] == key) {
            ans = mid;
            low = mid + 1;
        }
    }
    return ans;
}
let noKeyleastgreater = (a, key, low, high, ans = -1) => { // no need to find key
    while (low <= high) {
        let mid = low + (high - low + 1) / 2;
        if (a[mid] < key)low = mid + 1;
        else if (a[mid] > key) {
            ans = mid;
            high = mid - 1;
        }else if (a[mid] == key) low = mid + 1;
    }
    return ans;
}

let noKeygreatestlesser = (a, key, low, high, ans = -1) => {
    while (low <= high) {
        let mid = low + (high - low + 1) / 2;
        if (a[mid] < key) {
            ans = mid;
            low = mid + 1;
        } else if (a[mid] > key || a[mid] == key) high = mid - 1;
    }
    return ans;
}
Comments (0)