Understanding Binary Search Algorithm

Binary Search Algorithm
Binary Search Algorithm

Binary search is the most widely used searching algorithm mostly in a sorted list. Its time complexity is O(long). Brute force way to search an element is searching through the entire list until the element is found. Let’s see the implementation of both ways.

Naïve Way to Search for an element in an array:
bool search(int *arr, int x){
int n = arr.size();
for(int i = 0;i<n;i++)
if(arr[i] == x)
return true;
return false;
}
Time complexity: O(n) Space Complexity: O(1)

The basic idea behind Binary search is:

  • Find the mid and check if it is equal to the given element or not.
  • If the mid is less than the element to be found that means the element is larger and hence, we need to search in the right part of the array discarding the left one.
  • If the mid is more than the element to be found that means the element is smaller and hence, we need to search in the left part of the array discarding the right one.

Binary Searching algorithm: Iterative Algorithm
bool search(int *arr, int x){
int l = 0,h=arr.size()-1;
while(l<h){
int mid = l + (h-l)/2; //takes care of overflow for large integers
if(arr[mid] == x)
return true;
else if(arr[mid] < x) //search in right sub part
l = mid+1;
else
h = mid – 1; //search in left sub part
}
return false;
}
Time Complexity: O(logn) Space Complexity: O(1)

Binary Search Algorithm: Recursive Algorithm
bool search(int *arr, int l, int r, int x){
int mid = l + (h-l)/2;
if(arr[mid] == x)
return true;
return (search(arr,l,mid,x) || search(arr,mid+1,h,x);
//search in left sub part //search in right sub part
}
Time Complexity: O(logn) Space Complexity: O(n) (recursive stack)

Let us now see an example where it works on a monotonous function rather than a sorted list.
Painter’s Partition problem: this is a widely used classic example of binary search on unusual problems.
The problem statement is – We have to paint n boards of length {A1, A2…An}. There are k painters available and each takes 1 unit time to paint 1 unit of the board. The problem is to find the minimum time to get
this job done under the constraints that any painter will only paint continuous sections of boards say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

Solution:
Int painterNum(vector &C, long long x){
Long long sum = 0;
Long long num = 1;
For(auto c: C){
If(sum+c > X){
Sum = c; num++;
}else sum += c;
}
Return num;
}

Int paint(int A,int B,vector &C){
Int high = 0,low=0;
For(int x: C){
Low = max(x,low);
High += x;
}
While(low < high){ Long long mid = low + (high-low) >> 1; //divide by 2
If(painterNum(C,mid)<=A)high = mid;
Else low = mid + 1;
}
Return low;

}

Magnetic Basket Problem: In-universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.
Rick stated that magnetic force between two different balls at positions x and y is |x – y|.
Given the integer array position and the integer m. Return the required force.

Solution: Using Binary search
bool valid(vector &A, int M, int m) {
int prev = 0;
for (int i = 1, j = 1; i < m; ++i) { while (j < A.size() && A[j] < A[prev] + M) ++j; if (j >= A.size()) return false;
prev = j;
}
return true;
}
int maxDistance(vector& A, int m) {
sort(begin(A), end(A));
if (m == 2) return A.back() – A[0];
int L = 1, R = A.back() – A[0];
while (L <= R) {
int M = (L + R) / 2;
if (valid(A, M, m)) L = M + 1;
else R = M – 1;
}
return R;
}

These are the basic implementations and applications of binary search. Hope this helps an aspiring developer/programmer.

Explore more on Data Structures & Algorithms, here.

By Aniruddha Guin