Deep diving into Binary Search

What is Binary Search?

Binary Search, also known as logarithmic or half interval search, is a search algorithm that allows us to find the position of a target value within a sorted array.

The Binary Search will compare the target value to the middle element of an array and the target value is eliminated in the half that it can not lie and the remaining half is search, and the target is the compared to the middle element again.

Flowchart of Binary Search using iterative approach

Pseudocode:

array = [2, 4, 6, 8, 9, 14, 15]
find = 4
let low = 0 (return index)
let high = array.length - 1

therefore, 

binary_search(int[] array, int low , int high, int find)


while(low<=high)
middle = (low + (high -low)) / 2

if(find == array[middle])
return array[middle]

else if (find >= array[middle])
low = middle +1;

else if (find < array[middle])
high = middle - 1;

return -1

Code:

int binary_search(List<int> array, int findNumber, int low, int high) {
  while (low <= high) {
    double middle = (low + (high - low) / 2);
    int mid = middle.toInt();
    if (findNumber == array[mid]) {
      return mid;
    } else if (findNumber >= array[mid]) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

Big O Notation introduction

“Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation.”-Wikipedia.

Time and Space Complexity

1. Time complexity is the amount of time it takes for a sequence of code to execute.
2. Space complexity is how much space an algorithm takes.

Therefore, the time complexity for iterative approach for using binary search will be O(log(n)) while the space complexity will be O(1).

- Reason as to why the time complexity is O(log(n))

The array is being reduced to half while making search of the targeted value.

- Reason as to why the space complexity is O(1)

We are requiring 2 variables so as to keep track of the range of elements that are to be checked.

And that’s it! I hope this has helped you understand binary search using iterative method in dart.

To reach me:

LinkedIn: https://www.linkedin.com/in/faatimah-iz-zaahra-m-0670881a1/

X (previously Twitter): _fz3hra

GitHub: https://github.com/fz3hra

Cheers,

Umme Faatimah-Iz-Zaahra Mujore