Background:
Background:
Finding a character in the string is a very simple algorithm that could be asked in a phone interview or during initial coding rounds. Its a O(n) algo that will look for a character in the string and output it as soon as it finds it.
For ex:
- In string ‘Programming’, if we search for character r then it should return 1.
- Similarly if we search for character ‘z’ in string ‘Programming’ then it should return null.
This algorithm will find out a character in the string. If string is ‘Programming’, and if you want to find the character r. Then this algorithm will if the character r exists in the string. If you want to find out character ‘z’ then it will return ‘String not found’ since it is not present in the inputted string.
Algorithm:
- Find the length of the string and store it in len variable.
- Create a count variable, and initialize to 0.
- Compare character at each location start from count=0.
- Increment the count till len and keep comparing its character to inputted character.
- If character matches then break the loop.
Algorithm :
Step 1: Declare a character array ‘s’ and initialize it with the given string value “Programming”. char s[ ] = “programming”;
0 1 2 3 4 5 6 7 8 9 10
Step 2 : Declare a character variable ‘c’ and initialize it with the individual character to be searched for.
char c = ‘g’
Step 3: Declare and initialize a count variable with the value 0(zero).
int count = 0
Step 4: Find the length of the given string using strlen() method and assign the length value to the ‘len’ integer variable.
strlen(s) = 11
int len = 11;
Step 5: Using while loop, iterate through the character array to find whether the given individual character is present or not. If the character is matched, then print the count value otherwise increment the count value.
Iteration 1:
count = 0, len = 11
0 != 11 -> Condition true
0 1 2 3 4 5 6 7 8 9 10
IF : c = ‘g’, s[0] = ‘p’
‘g’ == ‘p’ -> Condition false
ELSE :
count = 1 (incremented by one)
Iteration 2:
count = 1, len = 11
1 != 11 -> Condition true
0 1 2 3 4 5 6 7 8 9 10
IF : c = ‘g’, s[1] = ‘r’
‘g’ == ‘r’ -> Condition false
ELSE :
count = 2 (incremented by one)
Iteration 3:
count = 2, len = 11
2 != 11 -> Condition true
0 1 2 3 4 5 6 7 8 9 10
IF : c = ‘g’, s[2] = ‘o’
‘g’ == ‘o’ -> Condition false
ELSE :
count = 3 (incremented by one)
Iteration 4:
count = 3, len = 11
3 != 11 -> Condition true
0 1 2 3 4 5 6 7 8 9 10
IF : c = ‘g’, s[3] = ‘g’
‘g’ == ‘g’ -> Condition true
Then,
Print the count value to console 3.
Enters the break statement, So terminate the loop.
Step 6: If the count reaches the end of string then print “Character not found” otherwise print “Character found”.
Count = 3, len = 11
IF: 3 == 11 -> Condition false
ELSE: Print “Character found” to the console.
Implementation:
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
char s[] = "Programming";
char c;
c = 'g';
int count = 0;
int len = strlen(s);
while(count!=len)
{
if(c == s[count])
{
std::cout<<count<<std::endl;
break;
}
else
count++;
}
if(count==len){
std::cout<<"Character not found"<<std::endl;
}
else {
std::cout<<"Character found"<<std::endl;
}
return 0;
}
Output :
Character found at Location: 3
Algorithm Complexity :
O(n)
No comments:
Post a Comment