JSFiddle - React, Tailwind, and code Playground

binary search original implementation in JS

by Yurii Predborskyi

JavaScript

// binary seach original algorithm

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
let search = function(nums, target) {
    // should return index of searched item, or -1 if item does not exist
    console.log(`looking for ${target} in ${nums}, length is ${nums.length}`)
    if (nums.length <= 0) {
        return -1;
    }
    let len = nums.length;
    let i = Math.floor(len / 2);
    let max = len;
    let min = 0;
    let repeats = 0;
    do {
        repeats++;
        console.log(`looking at ${i}, min ${min}, max ${max}`);
        if (nums[i] === target) {
            console.log(`${nums[i]} === ${target}, exiting`);
            return i;
        } else if (nums[i] > target) {
            max = i;
            console.log(`${nums[i]} > ${target}, looking back, new max is ${max}`);
            i = i - Math.max(Math.floor((max - min) / 2), 1);
        } else if (nums[i] < target) {
            min = i;
            console.log(`${nums[i]} < ${target}, looking forward, new min is ${min}`);
            i = i + Math.max(Math.floor((max - min) / 2), 1);
        }
    } while (i >= min && i < max);
    console.log(`target not found, exiting`);
    return -1;
};

let tests = [
    { nums: [-1,0,3,5,9,12], target: 9, answer: 4 },
    { nums: [-1,0,3,5,9,12], target: 2, answer: -1 },
    { nums: [5], target: 5, answer: 0 },
    { nums: [5], target: 3, answer: -1 },
    { nums: [2,5], target: 2, answer: 0 },
    { nums: [-1,0,5], target: 5, answer: 2 },
];

tests.forEach(test => {
    let res = search(test.nums, test.target);
    console.log(res, res === test.answer);
});

// clean variant
/*
var search = function(nums, target) {
    if (nums.length <= 0) {
        return -1;
    }
    let len = nums.length;
    let i = Math.floor(len / 2);
    let max = len;
    let min = 0;
    do {
        if (nums[i] === target) {
            return i;
        } else if (nums[i] > target) {
            max = i;
            i = i -...