Searching
In computer science, search operation is used for finding an item with specified properties among a collection of items.
Searching can be done in two ways
Sequential Search (Linear Search)
This is the most common algorithm which starts at the beginning and walk to the end, testing for a match at each item. This searching has the benefit of simplicity.
Pseudo code for sequential searching
int linearsearch (int a [ ], int first , int last, int key)
{
for (int i =first; i < = last; i ++) if (key==a [i])
{
return i ; // successfully found the
} // key and return location
}
return — 1; // failed to find key element
}
Flow Chart for Linear Search
Analysis of Sequential Search
The time complexity in sequential search in all three cases is given below Best case When we find the key on the first location of array, then the complexity is 0(1).
Worst case When the key is not found in the array and we have to scan the complete array, then the complexity is 0 (n).
Average case When the key could appear anywhere in the array, then a successful search will take total 1 + 2 + 3 +…+ n comparisons.
1 + 2 + 3 +…+ n = n (n + 1) comparisons
2
| Average number of comparisons = n | n + 1
________ x— 2 n |
Total number of comparisons number of items
n + 1
2
So, the time complexity = 0 (n)
Binary Search
In computer science, a binary search (half interval search) algorithm finds the position of a specified value with a sorted array. In each step, this algorithm divides the array into three sections
- Middle element
- Elements on left side of the middle element
- Elements on right side of the middle element
Then, check that if the middle element is the correct value, the searching stops, Otherwise go to the left side of the array if searching item is less than the middle element or go to the right side of the array if searching item is greater than middle element and this will go on until either the algorithm found the element or there are no elements to examine. This algorithm always look at the center value. Each time you get to discard half of the remaining list.
Pseudo Code of Binary Search
int binarysearch (int a[ ], int n, int key) {
int first = 0, last = n —1, middle;
while (first < = 1 ast)
{
middle= (first +last)/2;
/* calculate middle*/
if (a [middle]= value) /*
if value is found at mid */
{
return middle;
| else if (a [middle] > value) /*
if value is at left half */ last = middle — 1; |
| el se
first = middle + 1; /* if value is in right half */ return — 1; } |
Flow Chart for Binary Search
Analysis of Binary Search
The time complexity of binary search in all three cases is given below
Best case The best case complexity is 0(1) i.e., if the element to search is the middle element of the complete array. So, there is only one comparison required.
Average case This search cut the range in half every time.
T(n)= T(n/2) + 1
T(n) = T(n/22) + 2
Repeat upto K times, we get
T(n) = T(n/2K) + K
Let n = 2K ; T(n) = T(2K /2K) + K
T(n) = T(1) + K
T(n) = 1+ K // when array has one element, then it takes 0(1) time
T(n) = 0(K);
IIII n =2K = K = log2 n ; T(n) = 0 (log2 n)
Worst case In worst case, the complexity of binary search is O(log2n), because if element is not found but we have to run the algorithm, until there are no element in the array.