Searching Algorithm in DSA - Programmrs

 SEARCHING

• It is a process of finding an element within the list of elements stored in any order.
• It is not necessary that the data item we are searching for must be present in the list.
• If the searched item is present in the list then the searching algorithm (or program) can find that data item, in which case we say that the search is successful, but if the searched item is not present in the list, then it cannot be found and we say that the search is unsuccessful.

SEARCHING

Types of Searching:

1. Linear /Sequential Searching:

• It is the simplest technique to find out an element in an unordered list.
• We search for an element or value in a given array by traversing the array from the starting, till the desired element or value is found.
• Suppose there are ‘n’ elements organized sequentially on a List. The number of comparisons required to retrieve an element from the list purely depends on where the element is stored in the list. If it is the first element, one comparison will do; if it is the second element two comparisons are necessary, and so on. On average, you need [(n+1)/2] comparison‘s to search an element. If the search is not successful, you would need ‘n’ comparisons. The time complexity of the linear search is O (n).

ALGORITHM

Step 1 - Read the search element from the user.

Step 2 - Compare the search element with the first element in the list.

Step 3 - If both are matched, then display "Given element is found!!!" and terminate the function.

Step 4 - If both are not matched, then compare the search element with the next element in the list.

Step 5 - Repeat steps 3 and 4 until the search element is compared with the last element in the list.

Step 6 - If the last element in the list also doesn't match, then display "Element is not found!!!" and terminate the function.

Sequential search efficiency:

The number of comparisons of keys done in a sequential search of a list of length n is:

i. Unsuccessful search: n comparisons

ii. Successful search, best case: 1 comparison

iii. Successful search, worst case: n comparisons

iv. Successful search, average case : (n + 1)/2 comparisons

v. In any case, the number of comparisons is O(n)

2. Binary Search

• It is an extremely efficient algorithm.
• This search technique searches the given item in minimum possible comparisons.
• To do the binary search, first, we have to sort the array of elements.
• The logic behind this technique is given below. 
• First, find the middle element of the array.
• Compare the middle element with an item.
•  There are three cases:
•  If it is the desired element then a search is successful,
• If it is less than the desired item then search only in the first half of the array.
•  If it is greater than the desired item, search in the second half of the array.
• Repeat the same steps until an element is found or the search area is exhausted.

 Requirements:

• The list must be ordered.
• Rapid random access is required, so we cannot use binary search for a linked list.

 

 ALGORITHM

Given a table k of n elements in searching order searching for value x.

1. Initialize: low=0, high=n − 1
2. Perform Search: Repeat through step 4 while low <= high.
3. Obtain the index of the midpoint of the interval: mid=(low + high)/2
4. Compare:
• If X < k[mid]then high=mid − 1
• Else if X > k[mid]then low=mid + 1
• Else Write (“Search is successful”)
• Return (mid)
5. (“Search is unsuccessful”)
• Return
6. Finished 

Binary search efficiency:

• In all cases, the no. of comparisons is proportional to n. Hence, no. of comparisons in binary search is O (log n), where n is the no. of items in the list.
• Obviously, binary search is faster than sequential search, but there is extra overhead in maintaining the list ordered.
• Binary search is best suited for lists that are constructed and sorted once, and then repeatedly searched.