Searching in Design and Analysis of Algorithm Study Notes with Example

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.

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 last)

{

middle= (first +last)/2;

/* calculate middle*/

if (a [middle]= value) /*

if value is found at mid */

{

return middle;

}

else if (a [middle] > value) /* if values is at left half */

}

last =middle-1;

}

else

first=middle +1; /* if value is in right half */

return -1;

}

---

Flow chart of 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/2²) + 2

Repeat upto K times, we get

T(n) = T(n/2^K) + K

Let                                n = 2^K ; T(n) = T(2^K /2^K) + 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 =2^K = K = log₂ n ; T(n) = 0 (log₂ n)

Worst case In worst case, the complexity of binary search is O(log₂n), because if element is not found but we have to run the algorithm, until there are no element in the array.

---

Importance of Turing Machine Tutorial Notes Study Material with Examples

Follow Us on Social Platforms to get Updated : twiter,  facebook, Google Plus

Learn Turing Machine in Handbook Series:  Click here F