Binary Search
By: Nittyantt(Researcher)
Hashim(Designer)
What is Binary Search?
Binary search, also known as half-interval search, logarithmic search, or
binary chop in computer science, is a search technique that discovers the
position of a target value within a sorted array. The binary search compares
the target value to the array's middle element.
If they are not equal, the half in which the target cannot lie is discarded, and
the search resumes on the remaining half, comparing the centre element to
the target value again and again until the target value is discovered. If the
search results in the remaining half of the array being empty, the target is not
in the array.
Which is better Linear or Binary Search?
Binary search is faster than linear search except for small arrays. However, the
array must be sorted first to be able to apply binary search.
There are specialized data structures designed for fast searching, such as hash
tables, that can be searched more efficiently than binary search.
However, binary search can be used to solve a wider range of problems, such
as finding the next-smallest or next-largest element in the array relative to the
target even if it is absent from the array.
Variations of Binary Search:
1. Uniform binary search-Uniform binary search stores the difference in the index of the
middle element from the current iteration to the next iteration
2. Exponential search- Exponential search extends binary search to unbounded lists.
3. Interpolation search-Instead of calculating the midpoint, interpolation search estimates
the position of the target value. It works on the basis that the midpoint is not the best guess in
many cases.
4. Fractional cascading-Fractional cascading is a technique that speeds up binary searches
for the same element in multiple sorted arrays
5. Generalization to graphs-Binary search has been generalized to work on certain types of
graphs
6. Noisy binary search- Noisy binary search algorithms solve the case where the algorithm
cannot reliably compare elements of the array.
General Steps for binary Search.
The general procedures for binary search algorithm is given below.
The array in which searching will take place is:
1. Set two pointers to the lowest and highest places, respectively.
2. Find the array middle element, i.e. arr[(L + R)/2] = y.
3. If x equals mid, return mid. Otherwise, compare the element to be found with m.
4. If x > mid, compare it to the middle element on the right side of mid. This is accomplished by
adjusting low to low = mid + 1.
5. Otherwise, compare x to the centre element on the left side of mid. This is accomplished by
adjusting high to high = mid - 1.
6. Steps 3–6 should be repeated until low meets high.
7. Number is now found.
Pseudocode and Procedure for Binary Search:
function binary_search(A, n, T) is
Where an Array A of elements n elements with
L := 0 the data sorted as an arithmetic progression,
R := n − 1 and target value T.
while L ≤ R do The procedure:
m := floor((L + R) / 2)
1. Set L to 0 and R to n-1.
2. If L more than R return unsuccessful.
if A[m] < T then
3. Set m as middle position, which is less than
L := m + 1
or equal to L+ R/2 .
else if A[m] > T then 4. If Am< T set L to m+1 and go to step 2.
R := m − 1
else: 5. If Am> T set L to m-1 and go to step 2.
return m
6. Now Am = t.
return unsuccessful
Real life applications of Binary Search:
1. Find an element in a sorted array
2. Applications of Binary Search beyond arrays
2.1. To find if n is a square of an integer
2.2. Find the first value greater than or equal to x in a given array of sorted integers
2.3. Find the frequency of a given target value in an array of integer
3. Real life applications of Binary Search
3.1. Dictionary
3.2. Debugging a linear piece of code
3.3. Figuring out resource requirements for a large system
3.4. Find values in sorted collection
3.5. Semiconductor test programs
3.6. Numerical solutions to an equation
Video Representation:
Source : Video
This shows the various steps
Involved in Binary Search:
M is middle term
L is left limit
R is Right limit
Thank
you
