Python's bisect.bisect_right in TypeScript

How to use

Install via yarn add locutus and import: import { bisect_right } from 'locutus/python/bisect/bisect_right'.

Or with CommonJS: const { bisect_right } = require('locutus/python/bisect/bisect_right')

Use a bundler that supports tree-shaking so you only ship the functions you actually use. Vite, webpack, Rollup, and Parcel all handle this. For server-side use this is less of a concern.

Examples

These examples are extracted from test cases that automatically verify our functions against their native counterparts.

#	code	expected result
1	bisect_right([1, 2, 2, 4], 2)	3

Dependencies

This function uses the following Locutus functions:

• _bisect (python/_helpers)

Here's what our current TypeScript equivalent to Python's bisect.bisect_right looks like.

TSTypeScript JSJavaScript TSStandalone TS JSStandalone JS

Copy code

import { pythonBisectRight } from '../_helpers/_bisect.ts'

export function bisect_right(a: unknown, x: unknown, lo?: unknown, hi?: unknown): number {
  //      discuss at: https://locutus.io/python/bisect/bisect_right/
  // parity verified: Python 3.12
  //     original by: Kevin van Zonneveld (https://kvz.io)
  //       example 1: bisect_right([1, 2, 2, 4], 2)
  //       returns 1: 3

  return pythonBisectRight(a, x, lo, hi)
}

import { pythonBisectRight } from '../_helpers/_bisect.ts'

export function bisect_right(a, x, lo, hi) {
  //      discuss at: https://locutus.io/python/bisect/bisect_right/
  // parity verified: Python 3.12
  //     original by: Kevin van Zonneveld (https://kvz.io)
  //       example 1: bisect_right([1, 2, 2, 4], 2)
  //       returns 1: 3

  return pythonBisectRight(a, x, lo, hi)
}

// python/_helpers/_operator (Locutus helper dependency)
type NumericLike = number | boolean | bigint

function isNumericLike(value: unknown): value is NumericLike {
  return typeof value === 'number' || typeof value === 'boolean' || typeof value === 'bigint'
}

function toPythonNumber(value: unknown, functionName: string): number {
  if (typeof value === 'number') {
    return value
  }

  if (typeof value === 'boolean') {
    return value ? 1 : 0
  }

  if (typeof value === 'bigint') {
    const numericValue = Number(value)
    if (!Number.isSafeInteger(numericValue)) {
      throw new RangeError(`${functionName}() bigint values must fit within JS safe integer precision`)
    }

    return numericValue
  }

  throw new TypeError(`${functionName}() expected a numeric value`)
}

function toPythonInteger(value: unknown, functionName: string): bigint {
  if (typeof value === 'boolean') {
    return value ? 1n : 0n
  }

  if (typeof value === 'bigint') {
    return value
  }

  if (typeof value === 'number' && Number.isFinite(value) && Number.isSafeInteger(value)) {
    return BigInt(value)
  }

  throw new TypeError(`${functionName}() expected an integer value`)
}

// python/_helpers/_bisect (Locutus helper dependency)
type BisectSequence = unknown[] | string

function pythonBisectRight(sequence: unknown, item: unknown, lo?: unknown, hi?: unknown): number {
  return bisectCore(sequence, item, lo, hi, 'bisect_right', 'right')
}

function bisectCore(
  sequence: unknown,
  item: unknown,
  lo: unknown,
  hi: unknown,
  functionName: string,
  side: 'left' | 'right',
): number {
  const values = toBisectSequence(sequence, functionName)
  let left = normalizeLo(lo, functionName)
  let right = normalizeHi(hi, values.length, functionName)

  while (left < right) {
    const middle = Math.floor((left + right) / 2)
    const candidate = getSequenceItem(values, middle)

    if (
      side === 'left' ? pythonLessThan(candidate, item, functionName) : !pythonLessThan(item, candidate, functionName)
    ) {
      left = middle + 1
    } else {
      right = middle
    }
  }

  return left
}

function toBisectSequence(sequence: unknown, functionName: string): BisectSequence {
  if (Array.isArray(sequence) || typeof sequence === 'string') {
    return sequence
  }

  throw new TypeError(`${functionName}() expected an indexable sequence`)
}

function normalizeLo(value: unknown, functionName: string): number {
  if (value === undefined) {
    return 0
  }

  const index = toSequenceIndex(value, functionName)
  if (index < 0) {
    throw new RangeError('lo must be non-negative')
  }

  return index
}

function normalizeHi(value: unknown, sequenceLength: number, functionName: string): number {
  if (value === undefined || value === null) {
    return sequenceLength
  }

  return toSequenceIndex(value, functionName)
}

function toSequenceIndex(value: unknown, functionName: string): number {
  const index = Number(toPythonInteger(value, functionName))
  if (!Number.isSafeInteger(index)) {
    throw new RangeError(`${functionName}() index must fit within JS safe integer precision`)
  }

  return index
}

function getSequenceItem(sequence: BisectSequence, index: number): unknown {
  if (index < 0 || index >= sequence.length) {
    throw new Error(Array.isArray(sequence) ? 'list index out of range' : 'string index out of range')
  }

  return sequence[index]
}

function pythonLessThan(left: unknown, right: unknown, functionName: string): boolean {
  if (isNumericLike(left) && isNumericLike(right)) {
    const leftNumber = toPythonNumber(left, functionName)
    const rightNumber = toPythonNumber(right, functionName)
    if (Number.isNaN(leftNumber) || Number.isNaN(rightNumber)) {
      return false
    }

    return leftNumber < rightNumber
  }

  if (typeof left === 'string' && typeof right === 'string') {
    return left < right
  }

  throw new TypeError(`'<' not supported between instances of '${pythonTypeName(left)}' and '${pythonTypeName(right)}'`)
}

function pythonTypeName(value: unknown): string {
  if (typeof value === 'string') {
    return 'str'
  }

  if (typeof value === 'boolean') {
    return 'bool'
  }

  if (typeof value === 'bigint' || typeof value === 'number') {
    return 'int'
  }

  if (Array.isArray(value)) {
    return 'list'
  }

  if (value === null) {
    return 'NoneType'
  }

  if (value === undefined) {
    return 'undefined'
  }

  return typeof value
}

// python/bisect/bisect_right (target function module)
function bisect_right(a: unknown, x: unknown, lo?: unknown, hi?: unknown): number {
  //      discuss at: https://locutus.io/python/bisect/bisect_right/
  // parity verified: Python 3.12
  //     original by: Kevin van Zonneveld (https://kvz.io)
  //       example 1: bisect_right([1, 2, 2, 4], 2)
  //       returns 1: 3

  return pythonBisectRight(a, x, lo, hi)
}

// python/_helpers/_operator (Locutus helper dependency)
function isNumericLike(value) {
  return typeof value === 'number' || typeof value === 'boolean' || typeof value === 'bigint'
}

function toPythonNumber(value, functionName) {
  if (typeof value === 'number') {
    return value
  }

  if (typeof value === 'boolean') {
    return value ? 1 : 0
  }

  if (typeof value === 'bigint') {
    const numericValue = Number(value)
    if (!Number.isSafeInteger(numericValue)) {
      throw new RangeError(`${functionName}() bigint values must fit within JS safe integer precision`)
    }

    return numericValue
  }

  throw new TypeError(`${functionName}() expected a numeric value`)
}

function toPythonInteger(value, functionName) {
  if (typeof value === 'boolean') {
    return value ? 1n : 0n
  }

  if (typeof value === 'bigint') {
    return value
  }

  if (typeof value === 'number' && Number.isFinite(value) && Number.isSafeInteger(value)) {
    return BigInt(value)
  }

  throw new TypeError(`${functionName}() expected an integer value`)
}

// python/_helpers/_bisect (Locutus helper dependency)
function pythonBisectRight(sequence, item, lo, hi) {
  return bisectCore(sequence, item, lo, hi, 'bisect_right', 'right')
}

function bisectCore(sequence, item, lo, hi, functionName, side) {
  const values = toBisectSequence(sequence, functionName)
  let left = normalizeLo(lo, functionName)
  let right = normalizeHi(hi, values.length, functionName)

  while (left < right) {
    const middle = Math.floor((left + right) / 2)
    const candidate = getSequenceItem(values, middle)

    if (
      side === 'left' ? pythonLessThan(candidate, item, functionName) : !pythonLessThan(item, candidate, functionName)
    ) {
      left = middle + 1
    } else {
      right = middle
    }
  }

  return left
}

function toBisectSequence(sequence, functionName) {
  if (Array.isArray(sequence) || typeof sequence === 'string') {
    return sequence
  }

  throw new TypeError(`${functionName}() expected an indexable sequence`)
}

function normalizeLo(value, functionName) {
  if (value === undefined) {
    return 0
  }

  const index = toSequenceIndex(value, functionName)
  if (index < 0) {
    throw new RangeError('lo must be non-negative')
  }

  return index
}

function normalizeHi(value, sequenceLength, functionName) {
  if (value === undefined || value === null) {
    return sequenceLength
  }

  return toSequenceIndex(value, functionName)
}

function toSequenceIndex(value, functionName) {
  const index = Number(toPythonInteger(value, functionName))
  if (!Number.isSafeInteger(index)) {
    throw new RangeError(`${functionName}() index must fit within JS safe integer precision`)
  }

  return index
}

function getSequenceItem(sequence, index) {
  if (index < 0 || index >= sequence.length) {
    throw new Error(Array.isArray(sequence) ? 'list index out of range' : 'string index out of range')
  }

  return sequence[index]
}

function pythonLessThan(left, right, functionName) {
  if (isNumericLike(left) && isNumericLike(right)) {
    const leftNumber = toPythonNumber(left, functionName)
    const rightNumber = toPythonNumber(right, functionName)
    if (Number.isNaN(leftNumber) || Number.isNaN(rightNumber)) {
      return false
    }

    return leftNumber < rightNumber
  }

  if (typeof left === 'string' && typeof right === 'string') {
    return left < right
  }

  throw new TypeError(`'<' not supported between instances of '${pythonTypeName(left)}' and '${pythonTypeName(right)}'`)
}

function pythonTypeName(value) {
  if (typeof value === 'string') {
    return 'str'
  }

  if (typeof value === 'boolean') {
    return 'bool'
  }

  if (typeof value === 'bigint' || typeof value === 'number') {
    return 'int'
  }

  if (Array.isArray(value)) {
    return 'list'
  }

  if (value === null) {
    return 'NoneType'
  }

  if (value === undefined) {
    return 'undefined'
  }

  return typeof value
}

// python/bisect/bisect_right (target function module)
function bisect_right(a, x, lo, hi) {
  //      discuss at: https://locutus.io/python/bisect/bisect_right/
  // parity verified: Python 3.12
  //     original by: Kevin van Zonneveld (https://kvz.io)
  //       example 1: bisect_right([1, 2, 2, 4], 2)
  //       returns 1: 3

  return pythonBisectRight(a, x, lo, hi)
}

Improve this function

Locutus is a community effort following The McDonald's Theory: we ship first iterations, hoping others will improve them. If you see something that could be better, we'd love your contribution.

View on GitHub · Edit on GitHub · View Raw

---

Help us add more

Got a rainy Sunday afternoon and a taste for a porting puzzle?

• Get inspiration from the Python 3 standard library string page.
• Click "New file" in the appropriate folder on GitHub. This will fork the project to your account, directly add the file to it, and send a Pull Request to us.

We will then review it. If it's useful to the project and in line with our contributing guidelines your work will become part of Locutus and you'll be automatically credited in the authors section accordingly.

« More Python bisect functions

Star