Binary search on C++ string does not work.

Question

What is wrong with the following code? How come it does not found the letter using my implementation of a binary search?

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
#include <cwctype>
using namespace std;

bool contains(string s, char a){
  int m = 0;
  int n = s.length()-1;

  while (m != n) {
    int k = (m + n) / 2;
    if (s[k] == a)
      return true;

    if (s[k] < a) {
      n = k - 1;
    } else {
      m=k + 1;
    }
  }

  return false;
}

int main() {

  string s = "miyvarxarmaiko";
  char a = 'm';
  if (contains(s,a) == true) {
    cout << "s contains  character a" << endl;
  } else {
    cout << "does not contain" << endl;
  }

  return 0;
}

Answer 1

A prerequisite for binary search is that the array should be sorted.

To sort the string s you can do sort(s.begin(),s.end());

There are a few more bugs in your implementation:

if (s[k] < a) {
   n = k - 1; // Incorrect..should be m = k + 1
} else {
   m= k + 1;   // Incorrect..should be n = k - 1
}

Why?

When the key is greater than the middle element you need to narrow the search to the right half of the middle element and you do that changing the low(in your case m) to mid+1 (in your case k+1). Similarly the other case needs to be changed as well.

and

while (m!=n)

should be

while (m<=n)

Why?

Consider the case of searching char 'a' in the string "a". Both your m and n will be 0 and so will be k. In your case the while loop is not entered at all. So in general when the search narrows down to one element and that happens to be your key, your existing code will fail.

Tip:

Your variable name selection is not good. It better to use names such as low, high and mid.