Two binary search implements, one using recursion and another using loops. Quest from https://daily-quest-tau.vercel.app

binary-search.js

const binarySearch = (array, target) => {
	// min and max are indexes
	let min = 0 
	let max = array.length - 1
	// while loop will run until min and max cross each other
	while(min <= max) {
		// find middle index
		const middle = Math.floor((min + max) / 2)
		const current = array[middle]
		// determine if we need to search left or right or end if we found it
		if(target < current) max = middle - 1 // search left
		if(target > current) min = middle + 1 // search right
		if(target === current) return middle  // found it
	}
	// while loop ended without finding target
	return -1
}

const _binarySearch = (arr, target) => {
	if (arr.length === 0) return -1
	return rBinarySearch(arr, target, 0, arr.length - 1)
}

const rBinarySearch = (arr, target, min, max) => {
	if (min > max) return -1
	const middle = Math.floor((min + max) / 2)
	const current = arr[middle]
	// determine if we need to search left or right
	if (target < current) max = middle - 1 // search left
	if (target > current) min = middle + 1 // search right
	if (target === current) return middle  // found it

	// recursive call to search again left or right
	return rBinarySearch(arr, target, min, max)
}


module.exports = binarySearch

binary-search.test.js

const binarySearch = require('./binary-search');

describe('binarySearch', () => {
    it('should return -1 when the target integer is not found in the array', () => {
        expect(binarySearch([1, 2, 3, 4, 5], 6)).toBe(-1)
    })

    it('should return the correct index when the target integer is at the beginning of the array', () => {
        expect(binarySearch([1, 2, 3, 4, 5], 1)).toBe(0)
    })

    it('should return the correct index when the target integer is at the middle of the array', () => {
        expect(binarySearch([1, 2, 3, 4, 5], 3)).toBe(2)
    })

    it('should return the correct index when the target integer is at the end of the array', () => {
        expect(binarySearch([1, 2, 3, 4, 5], 5)).toBe(4)
    })

    it('should handle inputs with duplicate numbers in the array', () => {
        expect(binarySearch([1, 2, 2, 3, 4, 5], 2)).toBe(2)
    })

    it('should return the index of the target integer when duplicates are at the beginning of the array', () => {
        expect(binarySearch([2, 2, 3, 4, 5, 6], 2)).toBe(0)
    })

    it('should return the index of the target integer when duplicates are at the end of the array', () => {
        expect(binarySearch([1, 3, 4, 5, 6, 6], 6)).toBe(4)
    })

    it('should return the index of the target integer when duplicates are in the middle of the array', () => {
        expect(binarySearch([1, 3, 4, 4, 4, 5, 6], 4)).toBe(3)
    })

    it('should return the index of the target integer when there are multiple sets of duplicates', () => {
        expect(binarySearch([1, 1, 2, 2, 2, 3, 3, 4], 2)).toBe(3)
    })
})

package.json

{
  "name": "daily-quest",
  "version": "1.0.0",
  "description": "",
  "main": "index.js",
  "scripts": {
    "test": "jest"
  },
  "author": "",
  "license": "ISC",
  "devDependencies": {
    "jest": "^29.7.0"
  }
}