<<< Searching

1. Two Searching Techniques: e.g. 

1. Linear search O(n)

1. Special case of Brute force search O(2^n)

2. Linear searching Algorithm: e.g.

1. Input a list and an item

A[1 ..n], item = x, location = 0;

2. 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;

   }

 }

3. if(i > n) print "Not Found"

4. Output: "Found" or "Not Found"

2. Binary search O(n log n)

1. Finding a particular value in a linear array

2. Example of Divide and Conquer algorithm

3. Binary search process: e.g. 

1. Middle index = (1st index + Last index) / 2

4. Binary searching algorithm: e.g.

1. Input A[1 ...m], x (where we find x in the A list)

2. So, first = 1, last = m

3. 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

 }

4. If (first > last) print "Not found"

5. Output: "mid" or "Not found"

2. Complexity calculation for linear searching: e.g. 

1. Best Case: O(1)

2. Average Case: O(log n)

3. Worst Case: T(n) = T(n/2) + 1, By using master theorem O(log n)

#Programming #Algorithm #CodeAnalysis #Searching #AbdurRahimRatulAliKhan

>>>