Two Searching Techniques: e.g.
Linear search O(n)
Special case of Brute force search O(2^n)
Linear searching Algorithm: e.g.
Input a list and an item
A[1 ..n], item = x, location = 0;
Search the list to find the target element
for(i = 1; i <= n; i = i + 1)
{
if(A[i] = item)
{
Print "found"
Location = I;
Stop searching;
}
}
if(i > n) print "Not Found"
Output: "Found" or "Not Found"
Binary search O(n log n)
Finding a particular value in a linear array
Example of Divide and Conquer algorithm
Binary search process: e.g.
Middle index = (1st index + Last index) / 2
Binary searching algorithm: e.g.
Input A[1 ...m], x (where we find x in the A list)
So, first = 1, last = m
while(first <= last)
{
mid = (first + last) / 2;
i. if(x = A[mid]), then print "mid"
stop searching;
ii. else if (x < A[mid]) then last = mid - 1
iii. else first = mid + 1
}
If (first > last) print "Not found"
Output: "mid" or "Not found"
Complexity calculation for linear searching: e.g.
Best Case: O(1)
Average Case: O(log n)
Worst Case: T(n) = T(n/2) + 1, By using master theorem O(log n)
#Programming #Algorithm #CodeAnalysis #Searching #AbdurRahimRatulAliKhan
