DILI #8: This is BS.

Today, I will talk about BS. You've guessed it, it's Binary Search! Opposed to its more nonsensical cousin, BS is a really efficient and most definitely sensible algorithm to find an item from a sorted array or vector.

For starters, I did not do a good job covering array and just jumped to doing a problem. So, here we go. An array is like a list of items where you can store many of same type of data in one array. Imagine going into a supermarket, there are different sections for meats, vegetables, fruitsa and etc. Each of those sections is an array and they're storing something of their own types. So, a "meat" array can only store "meat" and nothing else but "meat".

The same thing also applies to vector but the only key difference is an array size/length has to be established beforehand. Whereas a vector size/length can grow or shrink dependent on the type of "meat" you took or put back.

That should brief the basics of array and vector. Now, we need to talk BS. BS works by dividing a sorted list in half repeatedly until you've reached the desired result. For example, try playing the higher lower number game. I will think of a number in a range and you can try to guess it. The most efficient way to do it every single time is to guess the halfway point. And everytime, we will get closer and closer to the answer by a half. And to put this in code, Here's a step-by-step description of using binary search to play the game above:

1. Let min = 1 and max = n.
2. Calculate the average.
3. If you guessed it, yay!.
4. If I say higher, set your min to that halfway point.
5. If I say lower, set your max to that halfway point.
6. Then rinse and repeat from step 2.

This is the simplest form of BS:

#include <iostream>
using namespace std;

int binarySearch(int array[], int x, int low, int high) {
  while (low <= high) {
    int mid = low + (high - low) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      low = mid + 1;

    else
      high = mid - 1;
  }

  return -1;
}

int main() {
  int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
   cout << "Not found";
  else
    cout << result;
  return 0;
}

With this, you can find the item in your list most efficiently. Just sort the array or vector and BS your way to the answer. With BS-ing in your skillset, you can make everyone gasped of how amazing you are!

REFERENCES:
GeeksforGeeks