TypeScript implementation of binary search and it's variant (less/less or equal)

binarySearch.ts

export function createExactFinder<T>(comp: (a: T, b: T) => number) {
  return (list: T[], target: T) => {
    let l = 0
    let r = list.length - 1

    while (l <= r) {
      const m = Math.ceil((l + r) / 2)
      const c = comp(list[m], target)

      if (c === 0) return m
      
      if (c > 0) {
        r = m - 1
      } else {
        l = m + 1
      }
    }

    return -1
  }  
}

export function createMaxLessFinder<T>(comp: (a: T, b: T) => number) {
  return (list: T[], target: T) => {
    let l = 0
    let r = list.length - 1

    while (l < r) {
      const m = Math.ceil((l + r) / 2)

      if (comp(list[m], target) >= 0) {
        r = m - 1
      } else {
        l = m
      }
    }

    if (comp(list[r], target) >= 0) return -1

    return r
  }  
}

export function createMaxLessOrEqualFinder<T>(comp: (a: T, b: T) => number) {
  return (list: T[], target: T) => {
    let l = 0
    let r = list.length - 1

    while (l < r) {
      const m = Math.ceil((l + r) / 2)

      if (comp(list[m], target) > 0) {
        r = m - 1
      } else {
        l = m
      }
    }

    if (comp(list[r], target) > 0) return -1

    return r
  }  
}


export function createMinGreaterFinder<T>(comp: (a: T, b: T) => number) {
  return (list: T[], target: T) => {
    let l = 0
    let r = list.length - 1

    while (l < r) {
      const m = Math.floor((l + r) / 2)

      if (comp(list[m], target) <= 0) {
        l = m + 1
      } else {
        r = m
      }
    }

    if (comp(list[r], target) <= 0) return -1

    return r
  }  
}

export function createMinGreaterOrEqualFinder<T>(comp: (a: T, b: T) => number) {
  return (list: T[], target: T) => {
    let l = 0
    let r = list.length - 1

    while (l < r) {
      const m = Math.floor((l + r) / 2)

      if (comp(list[m], target) < 0) {
        l = m + 1
      } else {
        r = m
      }
    }

    if (comp(list[r], target) < 0) return -1

    return r
  }  
}

Usage

interface Student {
  name: string
  age: number
}

const findLastStudentUntil = createMaxLessFinder<Student>((a, b) => {
  if (a.name > b.name) return 1
  if (a.name < b.name) return -1
  return a.age - b.age
})

const index = findLastStudentUntil(someSortedStudents, targetStudent)

• Every list for the parameter of these functions MUST be sorted under same comparator.
• createExactFinder
  • Create function which returns the index of exact element in list where such element satisfies comp(list[i], target) === 0
• createMaxLessFinder
  • Create function which returns the index of maximum element in list where such element satisfies comp(list[i], target) < 0
• createMaxLessOrEqualFinder
  • Create function which returns the index of maximum element in list where such element satisfies comp(list[i], target) ≤ 0
• createMinGreaterFinder
  • Create function which returns the index of minimum element in list where such element satisfies comp(list[i], target) > 0
• createMinGreaterOrEqualFinder
  • Create function which returns the index of minimum element in list where such element satisfies comp(list[i], target) ≥ 0