What is Binary Search?

[aastha]

What is Binary Search?

[aastha]

Binary search is a searching algorithm used for searching an element in sorted array. It proceeds by neglecting half the size of array and then recur the same searching process on the half-sized array.

Binary Search uses divide and conquer approach.

Steps Involved: –

Array- A, size of array- n, element to be searched- e.
1. Compare e with middle element of the array.
2. If e matches then, e is present at the middle position.
3. If e is less than middle element, then repeat STEP1 and STEP2 on left side of the A (i.e. elements present at left of middle element).
4. If e is greater than middle element, then repeat STEP1 and STEP2 on right side of the A (i.e. elements present at right of middle element).

Time Complexity

T(n)= T(n/2) + c
Comparing this to Master Method the above expression belongs to second case. Therefore time complexity of binary search is of the order O(log n).

Variation and Uses

1. Find first occurrence of an element.
This can be done by altering the termination condition.
a) Terminate when there is only one element left in A.
b) Terminate if middle element is equal to the key and element on the left of the middle element (A [mid -1]) is not equal to the key.

[Author]

Posts