A little bit about binary search

Algorithms are step-by-step well defined instructions accomplish a program or task. I chose to write and learning more about binary search, because it’s an interesting algorithm kind and help much for high performance for a program or task.

Suppose you’re looking up a phone number in the phone book, the owner name phone starts with L. You open the phone book in the middle and find the K letter phones list, you does know K is before L and eliminate almost half of phone book options.

Imagine a social network with millions of users, and you are try find a user starts with F. If when you try search about user starts with F, the social network programming search in all millions users, this does spend unnecessary time and resource for it.

📌 Binary search is a kind algorithm of does search and that minimize search options. But remember, it’s just does works with sorted lists.

Search a number

Suppose now, you’re search a number 32 in an array. You know that number 32 is near the middle, and you take a position that returns 42 number*. 42* is fewest that 32, so you can eliminate half numbers.

Now, you can have an array with three positions, and take a middle position again and that returns 20 number.

Now, you know 20 is fewest that 32, and left over one number for search, it’s 32!

Hands-on

Let’s see how to write binary search with Dart language. The binarySearch function takes an array and item, the function returns which position of item at array.

void main() {
  const list = [5, 20, 32, 43, 65, 88];

  print(binarySearch(list, 32)); // 2
  print(binarySearch(list, -1)); // null
}

int? binarySearch(List<int> list, int item) {
  // low and high to track search
  var low = 0;
  var high = list.length - 1;

  while (low <= high) {
    // check the middle of element
    var middle = low + high;
    var guess = list[middle];

    // If found them
    if (guess == item) return middle;
    // The guess is fewest than item
    if (guess < item)
      low = middle + 1;
    // The guess is higher than item
    else
      high = middle - 1;
  }

  // The item does not exists
  return null;
}