Find a string using binary search

Description: 

  1. Binary search searches either the left side or right side of the array depending on the search element. 
  2. The elements in the input array are always sequential. 
  3. Middle element is looked up if the element to be searched ‘x’ is < then mid element then left hand side of the array is searched. 
  4. If ‘x’ is > then mid element then the right hand side of the array is searched. 
  5. If mid element is ‘x’ then it is outputted
  6. This occurs recursively until the element is either found or array is exhausted. 




Algorithm:
Step 1: Declare and initialize a string array ‘s’ with the given sorted set of elements.
(Binary search works only on a sorted collection).
      0          1            2           3            4            5           6           7     
“at”
“”
“ball”
“”
“cat”
“”
“dog”
“”


Step 2: Declare and initialize a string variable ‘search’ with the target string value “dog” to
be searched for.
search = “dog”


Step 3: Declare and initialize ‘high’ and ‘low’ integer variables according to the length of the
given string array.
int low = 0
int high = 7


Step 4: Declare and initialize a variable ‘flag’ to find whether the target string is found or not.


Step 5: Using while loop, repeat step 6, step 7 and step 8 till the condition fails.


Step 6: Find the middle value, If it is an empty string then increment the middle value to the
next non-empty string.


Step 7: Compare the middle value with the given string using
targetString.compare(currentMiddleValue) method. This method,
1. returns 0(zero) if the target string is matched with the current middle value.
2. returns 1 if the target is greater than the current middle value
3. returns -1 if the target is less than the current middle value.


Step 8: If the compare() method’s return value is,
0 => Print “String found” and the index value. Then set the flag to 1 and break the loop.
1 => Set the low to the value next to the middle one. (Right part of the array)
-1=> Set the high to the value before to the middle one. (Left part of the array)


Step 9: Finally check whether the flag value is equal to 0, If the condition is true then print
“String not found” to the console.


Iteration 1: (step 5)
search = “dog”, low = 0, high = 7, flag = 0
0 < 7   -> Condition true
mid = (0+7)/2 (step 6)
mid = 7/2
mid = 3


    0           1           2           3           4           5           6           7
“at”
“”
“ball”
“”
“cat”
“”
“dog”
“”
(Left part)              mid               (Right part)


s[3] = “”
“”.empty() == true   -> Condition true
mid = 4 (Incremented by one)


    0           1           2           3           4           5           6           7
“at”
“”
“ball”
“”
cat
“”
“dog”
“”
          (Left part)               mid         (Right part)


s[4] = “cat”
i = “dog”.compare(“cat”) (step 7)
i = 1 (“dog” is greater than “cat”)
IF : 1==0   -> Condition false (step 8)
IF : 1==1   -> Condition true
Low = 5   (Right part)
IF : 1==-1   -> Condition false


Iteration 2: (step 5)
search = “dog”, low = 5, high = 7, flag = 0
5 < 7   -> Condition true
mid = (5+7)/2 (step 6)
mid = 12/2
mid = 6


    5           6           7
“”
dog
“”
  (Left)      mid     (Right)


s[6] = “dog”
“dog”.empty() == true   -> Condition false


i = “dog”.compare(“dog”) (step 7)
i = 0 (“dog” is equal “dog”)
IF : 0==0   -> Condition true (step 8)
Print “String found” to the console.
Print “Location: 7” to the console.
Set flag=1
Then break
Terminate the loop.


IF : flag = 1 (step 9)
1 == 0   -> Condition false.


Implementation:
//Searching the set of strings using binary search
#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <string>


using namespace std;


int main()
{
string s[10];
s[0] = "at";
s[1] = "";
s[2] = "ball";
s[3] = "";
s[4] = "cat";
s[5] = "";
s[6] = "dog";
s[7] = "";


string search = "dog";
int i;


int high = 7, low = 0,mid, flag = 0;


while(low <high)
{
mid = (low + high)/2;


//If the string is empty then go to the next non-empty string
if(s[mid].empty() == true)
mid++;


//Compare. 0 for true, -1 for smaller first char, 1 for bigger first char
i = search.compare(s[mid]);


//Found the string
if(i==0)
{
cout<<"String found\n";
cout<<"Location: "<<mid+1<<endl;
flag = 1;
break;
}
if(i==1)
{
//If the target is bigger than the current then go to the right part of the array
low = mid + 1;
}
if(i==-1)
{
//If the target is smaller than the current then go to the left part of the array
high = mid -1;
}
}
if(flag == 0)
cout<<"String not found";


getch();
return 0;
}


Output:
String found
Location: 7


Algorithm Complexity:
O(log n)


 

No comments:

Post a Comment

NoSQL

This one is reviewed but I need to delete its copy from hubpages or somewhere NoSQL Data models: key-value  Aggregate model.  key or i...