Description:
- Binary search searches either the left side or right side of the array depending on the search element.
- The elements in the input array are always sequential.
- 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.
- If ‘x’ is > then mid element then the right hand side of the array is searched.
- If mid element is ‘x’ then it is outputted
- 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
(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)
