Finding the location of the element with a given value or the record with a given key that is called searching. Operation of finding the location LOC of ITEM in data .Search is called successful if ITEM does appear in DATA and unsuccessful otherwise.
Searching Algorithm
- Linear search
- Binary search
Linear search
Which traverse DATA sequentially to locate ITEM is called linear search or sequential search.Find ITEM in in DATA where DATA contains n elements.Worst case occurs when must search through the entire array DATA. When ITEM does not appear in DATA. Algorithm require (n+1) comparisons. So running time proportional to n.
Binary search
That searching algorithm based on divide and conquer algorithm.Binary search have time complexity less than the linear search.Binary search work with sorted data.Number of comparison is less in binary search compared to the linear search.
Linear Search Algorithm
Step 1. Set DATA[N+1]=ITEM.
Step 2. Set LOC=1.
Step 3. Repeat while DATA[LOC]≠ ITEM
Set LOC=LOC+1.
Step 4. If LOC=N+1 then Set LOC=0.
Step 5. Exit.
Advantage of using Linear search algorithm in searching
- Work with unsorted data.
- Perform fast searches of small list.
- Not affected by insertions and deletions.
Disadvantage of using Linear search algorithm in searching
- Slow searching process.
- Time complexity in worst case O(n).
Example
DATA LIST 10,20,30,40,50
ITEM 40
Using linear search find element ITEM=40.
Solution
Initially LOC=1.
Repeat while DATA[LOC] ≠ 40
10≠ 40
LOC=LOC+1
Next Location is
20≠ 40
Next location is
30≠ 40
Next Location is
40=40
ITEM found.
search successful.
0 Comments