FOR FREE MATERIALS
Ubiquitous Binary Search
Back to ProgrammingDescription
Overview:
Binary Search: It is a searching algorithm that searches an element by repeatedly dividing the search interval into half. It works only on sorted data. Binary search follows the divide and conquer algorithm paradigm.
Ubiquitous Binary Search: The standard binary search algorithm has many variations. In this article we consider a variation where we reduce the number of comparisons in each iteration from two to one.
Prerequisites:
● Array
● Binary Search
Procedure:
The steps followed in this variant of binary search are
Step 1: Set low = 1, high = array_size
Step 2: Repeat Steps 3 to 4 while high - low > 1
Step 3: Set mid = low + (high - low) / 2
Step 4: If array[mid] <= search_item
Step 5: low = mid
Step 6: else
Step 7: high = mid
Step 8: If array[low] = search_item
Step 9: Index = low
Step 10: else
Step 11: Index = right
Consider an array of size 6 with search_item = 71 as shown in figure below
Algorithm
Algorithm:
Input:
1. Key & Value pairs
Output:
1. Perform insert, search, display operation on Hash Table
Algo:
Step 1: Start
Step 2: Defining ubiquitousBinarySearch function
voidubiquitousBinarySearch(intarr[], int low, int high, int item)
Set int mid <= null
While (high – low > 1) do
Set mid <= low + (high - low)/ 2
Check if(arr[mid] <= item)
Set low <= mid
Else
Set high <= mid
End If
End While
Check if (arr[low] = item)
Display “Element found at location” low
Else if (arr[high] = item)
Display “Element found at location” high
Else
Display “Element not found”
Step 3:Defining main function
Set int size<=null
Set int item <= null
Set intarr[100] <= null
Display “Enter number of elements”
Read size
Display “Enter the elements of the array”
for i = 0 to i < size repeat
Read arr[i]
Set i <= i + 1
Display “Enter search item”
Read item
Call ubiquitousBinarySearch(arr, 0, size – 1, item)
Step 4: Stop
Code
Characteristics:
● The algorithm follows Divide and Conquer algorithm paradigm
● The space complexity of the algorithm O(1).
● The algorithm is a variant of binary search with fewer number of iterations. During each iteration only one comparison is required.
● The time complexity of the algorithm isO(log n) where n is the number of elements.
● The algorithm works only for sorted input data set.
Application:
● Any application that requires an efficient search technique such as in databases, etc.
Advantage:
● The space complexity of the algorithm is O(1).
● The number of iteration during each iteration is least i.e. 1
Disadvantage:
● The algorithm works only for sorted input data set.
●
Complexity:
Time Complexity:
The time complexity of this variant of binary search is the same as the standard binary search algorithm i.e. O(log n) where n is number of elements.
Space Complexity:
The algorithm does not require extra space. Hence, the space complexity of the algorithm is O(1).
