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)