Divide and Conquer Algorithm�
Divide and Conquer is an algorithmic paradigm. A typical Divide and Conquer algorithm solves a problem using following three steps.
1. Divide: Break the given problem into
sub problems of same type.�2. Conquer: Recursively solve these sub problems
�3. Combine: Appropriately combine the answers
Amity School of Engineering & Technology
1) Binary Search is a searching algorithm. In each step, the algorithm compares the input element x with the value of the middle element in array. If the values match, return the index of middle. Otherwise, if x is less than the middle element, then the algorithm recurs for left side of middle element, else recurs for right side of middle element.
Amity School of Engineering & Technology
Binary Search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.
Amity School of Engineering & Technology
Calculating Time complexity:
At each iteration, the array is divided by half. So let’s say the length of array at any iteration is n
�
Amity School of Engineering & Technology
Assume After k divisions, the length of array becomes 1
Therefore Length of array = n⁄2k = 1 => n = 2k
Applying log function on both sides:
=> log2 (n) = log2 (2k)
Therefore, k = log2 (n)
Hence, the time complexity of Binary Search is
log2 (n)
Amity School of Engineering & Technology
Time complexity of Binary Search
Amity School of Engineering & Technology