Skip to content

Instantly share code, notes, and snippets.

@Revivedaniel

Revivedaniel/BinarySearch.md

Last active February 25, 2023 00:54
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Revivedaniel/063f18d218f094098c4a074bd1e1877c to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Revivedaniel/063f18d218f094098c4a074bd1e1877c to your computer and use it in GitHub Desktop.
Download ZIP
Raw
BinarySearch.md

Binary Search Algorithm

Given I have a sorted array, I want to find the index of a number within that array.

binarySearch(arr, target)

This algorithm will accept a sorted array and a target value. The array will only contain integers. The target might not be in the array, if this is the case return -1. The array will never be empty.

Examples

binarySearch([1,2,3,4,5],2)               // Return: 1
binarySearch([1,2,3,4,5],3)               // Return: 2
binarySearch([1,2,3,4,5],5)               // Return: 4
binarySearch([1,2,3,4,5],6)               // Return: -1
binarySearch([
  5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 
  40, 44, 64, 79, 84, 86, 95, 96, 98, 99
], 10)                                    // Return: 2
binarySearch([
  5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 
  40, 44, 64, 79, 84, 86, 95, 96, 98, 99
], 95)                                    // Return: 16
binarySearch([
  5, 6, 10, 13, 14, 18, 30, 34, 35, 37, 
  40, 44, 64, 79, 84, 86, 95, 96, 98, 99
], 100)                                   // Return: -1

Let's break it down!

The way that this binary search algorithm works is it starts by checking the middle value of the array.
If the value is equal to the target value, great! We found it on the first try.

If the value is greater than the target value, then we know that the value must be somewhere between the beginning of the array and the middle of the array.

If the value is less than the target value, then we know that the value must be somewhere between the middle and end of the array.

We repeat this logic several times until we either find the value or determine the value does not exist in the array.
Normally I would go into deep detail in this section but I'm going to switch things up and go into more detail as we pseudo code.

Pseudo Code

The first step in this solution is to define the start, middle, and end of the array in terms of indexes.

+// Define the start, middle, and end of the array.

After determining where the middle index would be, we should check to if the value at that index is equal to the target.

Since there is a possibility we will need to do this more than once, we should define a loop. The condition of that loop is it should run as long as the value at the middle index is not equal to the target value.

// Define the start, middle, and end of the array.
+// Loop while the middle value does not equal the target value.

In the case where the middle value is equal to the target value, this loop will stop and we should return the value of the middleIndex.

// Define the start, middle, and end of the array.
// Loop while the middle value does not equal the target value.
+  // Do something

+// return the middleIndex variable.

Next we will need to evaluate the middle value to see if it is larger or smaller than the target. We can do this within the loop since the loop will only run if the middle value is not equal to the taget.

The first condition will be if the middle value is less than the target then we should move the start index to one element after the middle element.

We are moving the start index to the middle index to shrink the window to only look at the values in the second half of the array. We are also moving the start index to one ahead of the middle because we already know that the middle value is less than the target and should not be in the window.

// Define the start, middle, and end of the array.
// Loop while the middle value does not equal the target value.
+  // if the middle element is less than the target value
+    // Move the start index to one element after the middle index

// return the middleIndex variable.

Now, the next condition will be if the middle value is less than the target then we should move the end index to one element before the middle element

We are moving the end index to the middle index to shrink the window to only look at the value in the first half of the array. We are also moving the end index to one before the middle because we already know that the middle value is greater than the target and should not be in the window.'```js

// Define the start, middle, and end of the array.
// Loop while the middle value does not equal the target value.
  // if the middle element is less than the target value.
    // Move the start index to one element after the middle index.
+  // if the middle element is greater than the target value.
+    // Move the end index to one element before the middle index.

// return the middleIndex variable.

Since we have now determined the new window to search in, we need to update the middle index to be the middle of the new window.

// Define the start, middle, and end of the array.
// Loop while the middle value does not equal the target value.
  // if the middle element is less than the target value.
    // Move the start index to one element after the middle index.
  // if the middle element is greater than the target value.
    // Move the end index to one element before the middle index.
+  // Update the middle index to be the middle of the new window.

// return the middleIndex variable.

Cool! This logic is strong but there is one flaw, what if the value does not exist? That would mean this loop will continue forever and your computer will not like you.

We need to add a condition to break the loop when the element doesn't exist. To accomplish this we need to first look at the logic one more time.

Since we move the start and end indexes to either 1 ahead or 1 behind the middle index, eventually the start and end indexes will swap and the start index will be greater than the end index.

That is a great place for the loop to stop. So, we will add a condition to the loop to check that the start index is less than or equal to the end index.

We want to to be less than or eqaul to because there is a chance where the last posible match is the target value. In this case the start, end, and middle indexes will all overlap on the same value which happens to be the target value.

// Define the start, middle, and end of the array.
// Loop while the middle value does not equal the target value.
+// and the start index is less than or equal to the end index.
  // if the middle element is less than the target value.
    // Move the start index to one element after the middle index.
  // if the middle element is greater than the target value.
    // Move the end index to one element before the middle index.
  // Update the middle index to be the middle of the new window.

// return the middleIndex variable.

One last thing. If the loop breaks because the start index is larger than the end, then the target does not exist in the array.

For this case we need to return -1 and if we only return the middle index, this would not be the true answer. We need to add some final logic outside the loop to check if the middle value is equal to the target value.

// Define the start, middle, and end of the array.
// Loop while the middle value does not equal the target value.
// and the start index is less than or equal to the end index.
  // if the middle element is less than the target value.
    // Move the start index to one element after the middle index.
  // if the middle element is greater than the target value.
    // Move the end index to one element before the middle index.
  // Update the middle index to be the middle of the new window.

+// if the middle value is equal to the target value, return the middle index
+// otherwise, return -1

Awesome!

Let's code!

First let's define out start, middle, and end variables.

function binarySearch(arr, target) {
  // Define the start, middle, and end of the array.
  let startIndex = 0;
  let endIndex = arr.length - 1;
  let middleIndex = Math.floor((startIndex + endIndex) / 2);
}

Notice the use of Math.floor here. Since the middle index of the current window might not always equal a whole number, we need to round the number somehow.

In my example I will be rounding down but you can round up and this will still work. the only thing is you need to be consitant with your rounding in that later you will be updating the middle index again and you need to round the same way every time.

Next, we are going to define the loop where the condition is that the middle value is not equal to the target value and that the start index is less than or equal to the end index.

function binarySearch(arr, target) {
  let startIndex = 0;
  let endIndex = arr.length - 1;
  let middleIndex = Math.floor((startIndex + endIndex) / 2);
  // Loop while the middle value does not equal the target value.
  // and the start index is less than or equal to the end index.
  while (arr[middleIndex] !== target && startIndex <= endIndex) {}
}

Now we can define the logic to check if the middle value is less than the target value.If this is true then we need to move the start index to one element after the middle element.

function binarySearch(arr, target) {
  let startIndex = 0;
  let endIndex = arr.length - 1;
  let middleIndex = Math.floor((startIndex + endIndex) / 2);
  while (arr[middleIndex] !== target && startIndex <= endIndex) {
    // If the middle element is less than the target value
    if (arr[middleIndex] < target) {
      // move the start index of the window to one element after the middle index.
      startIndex = middleIndex + 1;
    }
  }
}

If the middle element is not less than or equal to the target value then it must be greater than. In this case we will use an else statement and move the end index to the element before the middle index.

function binarySearch(arr, target) {
  let startIndex = 0;
  let endIndex = arr.length - 1;
  let middleIndex = Math.floor((startIndex + endIndex) / 2);
  while (arr[middleIndex] !== target && startIndex <= endIndex) {
    if (arr[middleIndex] < target) {
      startIndex = middleIndex + 1;
    } else {
      // Otherwise the element must be greater than the element 
      // and we should move the end index to one element before the middle index.
      endIndex = middleIndex - 1;
    }
  }
}

After we move the window we need to recalculate the middle value.

function binarySearch(arr, target) {
  let startIndex = 0;
  let endIndex = arr.length - 1;
  let middleIndex = Math.floor((startIndex + endIndex) / 2);
  while (arr[middleIndex] !== target && startIndex <= endIndex) {
    if (arr[middleIndex] < target) {
      startIndex = middleIndex + 1;
    } else {
      endIndex = middleIndex - 1;
    }
    // update the middle index
    middleIndex = Math.floor((startIndex + endIndex) / 2);
  }
}

Finally, outside the loop we will perform a quick check to see if the middle value is equal to the target value.

If this is true we will return the middle index and if not we return -1.

function binarySearch(arr, target) {
  let startIndex = 0;
  let endIndex = arr.length - 1;
  let middleIndex = Math.floor((startIndex + endIndex) / 2);
  while (arr[middleIndex] !== target && startIndex <= endIndex) {
    if (arr[middleIndex] < target) {
      startIndex = middleIndex + 1;
    } else {
      endIndex = middleIndex - 1;
    }
    middleIndex = Math.floor((startIndex + endIndex) / 2);
  }
  // Finally, if the element at the middle index is equal to the target then we return middle index
  if (arr[middleIndex] === target) {
      return middleIndex;
  }
  // Otherwise the element does not exist and we return -1
  return -1;
}

We now have a Binary Search algorithm!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment