What is Searching? Types of Searching
- Searching is the process of finding a given value position in a list of values.
- It decides whether a search key is present in the data or not.
- It is the algorithmic process of finding a particular item in a collection of items.
- It can be done on internal data structure or on external data structure.
- Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored.
Algorithms are generally classified into two categories:
Sequential Search:
In this, the list or array is traversed sequentially and every element is checked.
For example: Linear Search, Sentinel Linear Search
Interval Search:
These algorithms are specifically designed for searching in sorted data-structures.
These type of searching algorithms are much more efficient than Linear Search.
They repeatedly target the center of the search structure and divide the search space in half.
For Example: Binary Search, Fibonacci Search
Sequential Search (Linear Search)
- Sequential search is also called as Linear Search.
- Sequential search starts at the beginning of the list and checks every element of the list.
- It is a basic and simple search algorithm.
34 56 21 09 76 1 98 50
Suppose, key=34, we search it in array (where it is present or not in array)
Yes, It is present at arr[0] location that means we found it at 1st position,
We compare arr[i]==key and it takes O(1) time. This is the best time complexity of Linear search
Now we search key= 98, Again we compare arr[i]== key, it is located at 6th location, That means we get O(n) time complexity in average and worst case.
Pseudo Code: Linear Search
value=[2,5,6,9,1]
target= 9
function searchValue(value, target)
{
for (var i = 0; i < value.length; i++)
{
if (value[i] == target)
{
return i;
}
}
return -1;
}
Binary Search
- The binary search algorithm can be used with only a sorted list of elements.
- Binary search follows divide and conquer approach in which, the list is divided into two halves.
Algorithm:
This search process starts comparing the search element with the middle element in the list
If both are matched, then the result is "element found".
Otherwise, we check whether the search element is smaller or larger than the middle element in the list.
If the search element is smaller, then we repeat the same process for the left sublist of the middle element.
If the search element is larger, then we repeat the same process for the right sublist of the middle element.
if that element doesn't match with the search element, then the result is "Element not found in the list".
Example:
1.The array in which searching is to be performed is:
Let, x= 4 element to be searched.
2. Set two pointers low and high at the lowest and the highest positions respectively. Ie., low= 0 and high =6
3. Find the element mid of the array ie. ([low+high])/2 =3 ie mid at 3rd location
4. If x == arr[mid], then return mid. Else, compare the element to be searched with mid.
Ie. 4==6
5. If x>arr[mid] compare x with middle element of the elements of the right side of mid. Ie 4>6….?
This is done by setting low to low= mid+1
6. Else, compare x with the middle of the elements on the left side of mid.
7. Repeat steps 3 to 6 until low meets high
8. x=4 is found
Pseudo Code:
This can be implemented in two ways which are discussed below.
Iterative Method
Recursive Method
Iterative Method
do until the pointers low and high meet each other.
mid = (low + high)/2
if (x == arr[mid])
return mid
else if (x > A[mid]) // x is on the right side
low = mid + 1
else // x is on the left side
high = mid - 1
Recursive Method
The recursive method follows the divide and conquer approach.
binarySearch(arr, x, low, high)
if low > high
return False
else
mid = (low + high) / 2
if x == arr[mid]
return mid
else if x < data[mid] // x is on the right side
return binarySearch(arr, x, mid + 1, high)
else // x is on the right side
return binarySearch(arr, x, low, mid - 1)
This is done by setting high to high= mid-1. ie. high = 3-1=2
Time Complexity:
Linear search time complexity is O(n).
Where Binary search has O(logn).
Fibonacci Search
Similarities with Binary Search:
Works for sorted arrays
A Divide and Conquer Algorithm.
Has Log n time complexity.
Differences with Binary Search:
Fibonacci Search divides given array in unequal parts
Binary Search uses division operator to divide range. Fibonacci Search doesn’t use /, but uses + and -. The division operator may be costly on some CPUs.
Fibonacci Search examines relatively closer elements in subsequent steps. So when input array is big that cannot fit in CPU cache or even in RAM, Fibonacci Search can be useful.
This is based on Fibonacci series :
F(n+1)=F(n)+F(n-1)
where F(i) is the ith number of the Fibonacci series where F(0) and F(1) are defined as 0 and 1 respectively.
The first few Fibonacci numbers are:
0,1,1,2,3,5,8,13....
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 1 + 2 = 3 and so continues the series
Algorithm: Let the length of given array be n [0...n-1] and the element to be searched be x.
Find the smallest Fibonacci number greater than or equal to n. Let this number be fb(M) [m’th Fibonacci number]. Let the two Fibonacci numbers preceding it be fb(M-1) [(m-1)’th Fibonacci number] and fb(M-2) [(m-2)’th Fibonacci number].
While the array has elements to be checked:
-> Compare x with the last element of the range covered by fb(M-2)
-> If x matches, return index value
-> Else if x is less than the element, move the third Fibonacci variable two Fibonacci down, indicating removal of approximately two-third of the unsearched array.
-> Else x is greater than the element, move the third Fibonacci variable one Fibonacci down. Reset offset to index. Together this results into removal of approximately front one-third of the unsearched array.
Since there might be a single element remaining for comparison, check if fbM1 is '1'. If Yes, compare x with that remaining element. If match, return index value.
Example:
Let the length of given array be n [0...n-1] and the element to be searched be x.
0 1 2 3 4 //index
2 3 5 7 8 // value
x=7 int arr[10];
N = sizeof(arr)/sizeof(arr[0])= 5
// Initialize fibonacci numbers
fibonacci(int arr[], int x, int n)
{
fbM2 = 0 // (m-2)'th Fibonacci number
fbM1 = 1; // (m-1)'th Fibonacci number
fbM = fbM2 + fbM1; // m'th Fibonacci
// Marks the eliminated range from front
offset = -1;
// fbM is going to store the smallest Fibonacci
number greater than or equal to n
while (fbM < n)
{
fbM2 = fbM1;
fbM1 = fbM;
fbM = fbM2 + fbM1;
}
// fbM is going to store the smallest Fibonacci
number greater than or equal to n
while (fbM < n)
{
fbM2 = fbM1;
fbM1 = fbM;
fbM = fbM2 + fbM1;
}
// fbm=0+1=1;
while (2 < 5)
{
fbM2 =1 ;
fbM1 = 2;
fbM = 3;
}
while (3 < 5)
{
fbM2 =2 ;
fbM1 = 3;
fbM = 5;
}
//while there are elements to be inspected. Note that we compare arr[fibM2] with x.
When fbM becomes 1, fbM2 becomes 0
while (fbM > 1) // 5>1
{
int i = min(offset+fbM2, n-1); // min(-1+2,4)
i=1
int min(int x, int y)
{
return (x<=y)? x : y;
}
if (arr[i] < x) // 3<7
{
fbM = fbM1; fbM=3
fbM1 = fbM2; fbM1=2
fbM2 = fbM - fbM1; fbM2= 1
offset = i; offset=1
}
else if (arr[i] > x)
{
fbM = fbM2;
fbM1 = fbM1 - fbM2;
fbM2 = fbM - fbM1;
}
else return i;
//element found. return index
} // close while loopif (arr[i] < x) // 3<7
{
fbM = fbM1; fbM=3
fbM1 = fbM2; fbM1=2
fbM2 = fbM - fbM1; fbM2= 1
offset = i; offset=1
}
while (fbM > 1) // 3>1
{
int i = min(offset+fbM2, n-1); // min(1+2,4)
i=3
if (arr[i] < x) // 7<7
{
fbM = fbM1;
fbM1 = fbM2;
fbM2 = fbM - fbM1;
offset = i;
}
else if (arr[i] > x) // 7>7
{
fbM = fbM2;
fbM1 = fbM1 - fbM2;
fbM2 = fbM - fbM1;
}
else return i;
//element found. return index
} // close while loop/* comparing the last element with x */
if(fbM1 && arr[offset+1]==x)
return offset+1;
/*element not found. return -1 */
return -1;
- Worst case time complexity: O(logn)
- Average case time complexity: O(logn)
- Best case time complexity: O(n)
- Space complexity: O(1)
