I was just going through the basics and I wanted to verify that I still knew how to do a binary search. If I remember correctly these are the steps:

– Set a left pointer at the beginning of the sorted array

– Set a right pointer at the end of the sorted array

– Calculate the middle between those two pointers(If there is no exact middle, truncate the number) and set the a middle pointer there

– Check if the middle is the number you are looking for. If it is return

– If the element at middle is greater than the element you are looking for set the left pointer to middle + 1

– If the element at middle is lower than the element you are looking for set the right pointer to middle – 1

– Repeat until the number is found or left is greater than right (not found)

Here is the implementation in JS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
var array = [1, 2, 3, 4, 6, 7, 9, 22, 44, 66, 77, 99, 989, 1345, 7777, 7779, 9999, 10000000];

function binarySearch(needle, haystack) {
  function search(needle, haystack, left, right) {
    if (left > right) {
      return -1;
    }

    // We do left + ((right - left) / 2) instead of the simpler
    // (right + left) / 2 to avoid an overflow when right + left
    // becomes too big
    var middle = parseInt(left + ((right - left) / 2), 10);

    if (haystack[middle] === needle) {
      return middle;
    }

    if (haystack[middle] > needle) {
      return search(needle, haystack, left, middle - 1);
    }

    if (haystack[middle] < needle) {
      return search(needle, haystack, middle + 1, right);
    }
  }

  return search(needle, haystack, 0, haystack.length -1);
}

console.log(binarySearch(1, array)); // Found in 0
console.log(binarySearch(2, array)); // Found in 1
console.log(binarySearch(10000000, array)); // Found in 17
console.log(binarySearch(77, array)); // Found in 10
console.log(binarySearch(54, array)); // Not found (-1)
[ computer_science  algorithms  javascript  programming  ]
Sorting algorithms computer_science algorithms javascript programming
Raft for reaching consensus computer_science algorithms
The Rabin-Karp algorithm computer_science algorithms javascript programming
House painting problem computer_science algorithms javascript programming
Bitwise operations in Javascript algorithms javascript programming