Searching techniques in Data Structure And Algorithm

Searching techniques in Data Structure And Algorithm

• 1.
  SEARCHING TECHNIQUES DATA STRUCTUREAND ANALYSIS Instructor Pir Syed M Ayaz Farid Shah
• 2.
  What is searching? Searching is an operation or a technique that helps finds the place of a given element or value in the list. Any search is said to be successful or unsuccessful depending upon whether the element that is being searched is found or not.
• 3.
  Searching Techniques There aretow types of searching in data structure and analysis  Linear Search  Binary Search  Interpolation Search
• 4.
  Linear Search Linear searchis a very simple search algorithm. In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.
• 5.
  Linear Search Algorithm Linear Search ( Array A, Value x)  Step 1: Set i to 1  Step 2: if i > n then go to step 7  Step 3: if A[i] = x then go to step 6  Step 4: Set i to i + 1  Step 5: Go to Step 2  Step 6: Print Element x Found at index i and go to step 8  Step 7: Print element not found  Step 8: Exit
• 6.
  Binary search Binary searchis a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form. Binary search looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the right of the middle item. Otherwise, the item is searched for in the sub-array to the left of the middle item. This process continues on the sub-array as well until the size of the subarray reduces to zero.
• 7.
  Binary Search Algorithm Compare x with the middle element.  If x matches with middle element, we return the mid index.  Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.  Else (x is smaller) recur for the left half.
• 8.
  Binary vs. LinearSearch •Input data needs to be sorted in Binary Search and not in Linear Search •Linear search does the sequential access whereas Binary search access data randomly. •Time complexity of linear search -O(n) , Binary search has time complexity O(log n). • Linear search performs equality comparisons and Binary search performs ordering comparisons
• 9.
  Interpolation Search Interpolation searchis an improved variant of binary search. This search algorithm works on the probing position of the required value. For this algorithm to work properly, the data collection should be in a sorted form and equally distributed. Binary search has a huge advantage of time complexity over linear search. Linear search has worst-case complexity of Ο(n) whereas binary search has Ο(log n). There are cases where the location of target data may be known in advance. For example, in case of a telephone directory, if we want to search the telephone number of Morphius. Here, linear search and even binary search will seem slow as we can directly jump to memory space where the names start from 'M' are stored.
• 10.
  Interpolation Search Algorithm Step1 − Start searching data from middle of the list. Step 2 − If it is a match, return the index of the item, and exit. Step 3 − If it is not a match, probe position. Step 4 − Divide the list using probing formula and find the new midle. Step 5 − If data is greater than middle, search in higher sub-list. Step 6 − If data is smaller than middle, search in lower sub-list. Step 7 − Repeat until match.
• 11.
  Binary vs. InterpolationSearch  Positioning in Binary Search  Position Probing in Interpolation Search
• 12.
  ???