binary search function

[jessicacats]

I have never written or seen a binary search function before, so how would I write one using vectors full of a file (the file is alphabetical)

[keskiverto]

http://www.cplusplus.com/reference/algorithm/binary_search/

[jessicacats]

would something like this be close?

bool search(const vector<string>& v_word, const string& word)
{
	vector<string> v_word; // Declare a vector for the dictionary
	string word;
	vector<string>::iterator it;
	
	word(v.begin(), v.end());

	
	if (*it(v.begin(), v.end())){
		cout << "found!\n";
	}
	else {
		std::cout << "not found.\n";
	}

	return word;
}

[mbozzi]

The defining characteristic of a binary search is that, each iteration of the search process eliminates half of the possible candidates.

Let's assume I ask you to pick a random integer in [0, 16), without sharing. I can always find your choice by asking no more than ceil(lg(16)) = 4 yes-or-no ("binary") questions, assuming that you aren't being sneaky.

Let's assume you pick the number 6, but I don't know that.
I'll ask you the four questions in order - I know that your choice is in [0, 16), so I'll take that range and cut it in half:
1. Is your choice less than 8? You answer "yes".
I know that everything above 8 isn't an option, so now your choice must be in [0, 8). I'll split the available range in half:
2. Is your choice less than 4? You answer "no".
Now I know that your choice is in [4, 8) -- so I'll cut it in half:
3. Is your choice less than 6? You answer "no".
Now I know your choice is in [6, 8) -- so I'll cut the range in half:
4. Is your choice less than 7? "You answer "yes", which leaves the range of exactly one element - your choice is the single value in [6, 7): 6.

Logarithmic search is a kind of graph (or tree) traversal, and I almost always write graph traversals recursively. How you do it is up to you.

Edit: since someone else posted code immediately (< 1 minute) after I wrote this answer, I suppose there's no reason to not share this:

# include <vector>
# include <string>
# include <iostream>

# include <numeric>
# include <algorithm>
# include <cassert>

namespace {
  bool binary_search_impl(std::vector <int> const &v,
                          int const &search_for,
                          int const lower, int const upper) {
    /* Physically the middle element of the range we're looking for. */
    auto const &middle_it   = (lower + ((upper - lower) / 2));
    auto const &middle_elem = v.at(middle_it);

    std::cout << "Searching the range [" << lower << ", " << upper << ")\n";

    std::cout << "Checking the middle element, " << middle_elem << ": ";
    if (middle_elem == search_for) /* Did we find it... */
      return true;
    else if ((upper - lower) <= 1) /* ...or look at the last spot and fail? */
      return false;

    /* If we've not found it nor looked at the last spot, cut the range in half.
       First ask the question to determine which half it's in: */
    std::cout << "Is search_for (which is " << search_for
              << ") less than " << middle_elem << "?  ";
    if (search_for < middle_elem) {
      std::cout << "Yes.\n";
      std::cout << "Keeping only the candidates in [" << lower
                << ", " << middle_it << "): ";
      return binary_search_impl(v, search_for, lower, middle_it);
    } else {
      std::cout << "No.\n";
      std::cout << "Keeping only the candidates in [" << middle_it
                << ", " << upper << "): ";
      return binary_search_impl(v, search_for, middle_it, upper);
    }

  }
}

/* This just calls binary_search_impl with the right arguments. */
bool binary_search(std::vector <int> const &v,
                   int const &search_for) {
  /* If your data's not sorted, binary search isn't going to work! */
  assert(std::is_sorted(v.begin(), v.end()));
  /* Search the vector range [lower, upper) for search_for. */
  return binary_search_impl(v, search_for, 0, v.size());
}

int main() {
  std::vector<int> v(16);

  /* Fill v with with integers [0, 1, ... 15]. */
  std::iota(v.begin(), v.end(), 0);
  for (int i = 0; i < 16; ++ i) {
    std::cout << "Looking for " << i << ":\n";
    if (binary_search(v, i))
      std::cout << "Found it!\n";
    else
      std::cout << "Didn't find it!\n";
    std::cout << "\n\n";
  }
}