double_binary.cpp

// double_binary.cpp
// Search string vector to binary search

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

using namespace std;

int main()
{
	vector<string> str_array;
	string str = "AAAAAA";
	string find_text = "AADAGH";
	uint32_t loop = 0;

	for (int i = 0; i < 100000; i++)
	{
		str[5] = 'A' + i % 26;
		str[4] = 'A' + (i / 26) % 26;
		str[3] = 'A' + i / (26 * 26) % 26;
		str[2] = 'A' + i / (26 * 26 * 26) % 26;
		str[1] = 'A' + i / (26 * 26 * 26 * 26) % 26;
		str[0] = 'A' + i / (26 * 26 * 26 * 26 * 26) % 26;

		str_array.push_back(str);
	}

	cout << "AAAAAA ~ " << str_array[str_array.size()-1] << endl;

	for (size_t i = 0; i <= str_array.size(); i++)
	{
		if (i == str_array.size())
		{
			cout << "linear search loop : " << loop << " (not found)." << endl;
			break;
		}

		loop++;
		if (!str_array[i].compare(find_text))
		{
			cout << "linear search loop : " << loop << endl;
			break;
		}
	}

	loop = 0;
	uint32_t s, e, c;
	s = 0, e = str_array.size() - 1;

	for (size_t idx = 0; ; idx++)
	{
		uint32_t s1, s2, e1, e2;

		if (!find_text[idx])
		{
			if (str_array[s].compare(find_text))
			{
				cout << "double binary search loop : " << loop << " (not found)." << endl;
				break;
			}
			else
			{
				cout << "double binary search loop : " << loop << endl;
				break;
			}
		}
		s1 = s;
		e1 = e;
		while (1)
		{
			loop++;
			if (s1 >= e1)
			{
				s = s1;
				break;
			}
			else if (find_text[idx] == str_array[s][idx])
				break;

			c = (s1 + e1) / 2;

			if (find_text[idx] <= str_array[c][idx])
				e1 = c;
			else if (find_text[idx] > str_array[c][idx])
				s1 = c + 1;
		}
		s2 = s;
		e2 = e;
		while (1)
		{
			loop++;
			if (s2 >= e2)
			{
				e = e2;
				break;
			}
			else if (find_text[idx] == str_array[e][idx])
				break;

			c = (s2 + e2) / 2;

			if (find_text[idx] >= str_array[c][idx])
				s2 = c + 1;
			else if (find_text[idx] < str_array[c][idx])
				e2 = c - 1;
		}
	}

    return 0;
}