Searching problems

Search: As already known array elements are accessed using indices ,the process of finding the index of given element ,given element value is called a search operation.
Types of searching:
  1. Linear search
  2. binary search
  3. Tri-nary search e.t.c
In Method in python:
This is a in built method in python which returns element is present in list or not.
Syntax:
element in list_name
Return value:
The return value of this method are True or false
If element is in list it returns True
If element is not in list it returns false
A=[1,3,4,5,6 ]
print( 1 in A)
# it prints True as 1 in A
A=['1',2,3,4]
print(1 in A)
# the above print statement prints False as '1' not in A
# we can infer from this statement that '1' not equal to 1
Index method:
Index: This is a in built method in python which returns Zero based index of an element.
Syntax:
list_name.index(element)
Return value:
The return value is index if element is present in list else it return a Zero
A=[1,2,3,4]
print(A.index(2))
# it prints 1
print(A.index('mickey')
# it prints 0 as element is not in list
A Variation of Index method:
RINDEX:
This method returns last occurrence of element.
Syntax:
List_name.rindex(element)
Return value:
The return value is index if element is present in list else it return a Zero
A=[1,2,3,4,2]
print(A.index(2))
# it prints 4
print(A.index('mickey')
# it prints 0 as element is not in list
Unlike python C doesn't have in built methods for element search, so we use algorithms like linear search and binary search
LINEAR SEARCH:
PROCESS :
Consider an element whose index is to be found and a element with some values.
Iterate through the array using a for loop during each iteration check whether number at that position is equal to element need to be found or not if equal stop search and print index
main()
{
int a[10]={1,2,3,4,5,6,7,8,9,0};
int i,key_to_be_found=9;
int index=-1;
for(i=0;i<10;i++)
{
if(a[i] == key_to_be_found)
{
index=i;
break;
}
}
printf("index is %d",index);
}
This process prints -1 if element is not in array.
Time Complexity of this search is O(n) where n is number of elements.
Binary search:
NOTE :BINARY SEARCH IS APPLIED ONLY ON ARRAY WHICH IS IN ASCENDING ORDER..
This process reduces the comparisons to log(n).
If there are 8 elements in a array, if we do linear search we need 8 comparisons, but by using binary search on array number of comparisons reduces to 3.
Algorithm:
  • here we use "mid" variable to point to mid position of array
  • find mid element, check whether element_to_find is a[mid]
  • mid=low+(high-low)/2
  • where low and high are first and last indices
  • initially low=0,high=number of elements
  • if mid index value is less than required then we don't need to check elements which are before mid index
  • i.e,binary search(right array)
  • In the same way if mid value is greater than required, we don't need to check elements after that
  • Binary search(left array)f
  • Hence this reduces number of comparisons to log(n)
  • Repeat this process until we find element.
  • If element is not in array then loop stops without printing anything.
main()
{
int low=0,high=10;
int a[10]={1,2,3,4,5,6,7,8,9,10};
int mid,element_to_be_found,flag=0;
while(low
{
mid=low+(high-low)/2;
if(a[mid]==element_to_be_found)
{
printf("element Found at index %d",mid);//element is at mid position
flag=1;//To indicate that we found element
}
else if(a[mid] < element_to_be_found)//element is greater than mid so we check only right sub array so low is moved to mid+1
low=mid+1;
else
high=mid-1;//element is lesser than mid value so we check only left array
}
if(flag==0)//this mean we didn't find the element
printf("element not found");
}
PRACTICE PROBLEMS:
https://practice.geeksforgeeks.org/problems/binary-search/1
https://www.geeksforgeeks.org/find-index-first-1-sorted-array-0s-1s/
Do practice these problems from GEEKS FOR GEEKS to be clear about topic
Happy coding....
thank you