10 Replies - 447 Views - Last Post: 06 July 2013 - 09:39 PM Rate Topic: -----

#1 crodr  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 06-July 13

Binary search of array problem

Posted 06 July 2013 - 06:29 PM

I am trying to create a function that will find the index in an array through a binary search. I've attempted everything I can think of and am now only trying to see if the function returns the right index before I continue with the function its actually supposed to assist. It still won't return the right index so there must be something wrong with my logic. Here is my code to find the index in an array where I will place a string. The array is built interactively so this function has to be able to find the index whether the array is of size 0 or 1000000. The string key is the string that should be compared to the strings already in the array. Sorry if my if statements are unorganized but I assumed they must've been the problem so I kept messing with them. If any more information is needed let me know. Thank you.

int StringList::findIndex(string key, int start, int end)
{
	if( numberOfStrings == 0)
	{
		return 0;
	}
	if(numberOfStrings == 1)
	{
		if(str[0].compare(key) > 0)
		{
			return 0;
		}
		else if(str[0].compare(key) < 0)
		{
			return 1;
		}
	}
	else
	{
		static bool checkfirsthalf = false;
		static bool checksecondhalf = false;
		static int middle;
		middle = ((start + end)/2);
		if(end == -1)
		{
			return 0;
		}
		if(start > end)
		{
			return start;
		}
		if(str[middle].compare(key) < 0)
		{
			checksecondhalf = true;
		}
		if(str[middle].compare(key) > 0)
		{
			checkfirsthalf = true;
		}
		if(middle == 0 && checkfirsthalf == true)
		{
			return 0;
		}
		if(str[middle].compare(key) == 0)
		{
			return middle;
		}
		else if(checkfirsthalf)
		{
			return findIndex(key, start, middle-1);
		}
		else if(checksecondhalf)
		{
			return findIndex(key, middle+1, end);
		}
	}
}


Is This A Good Question/Topic? 0
  • +

Replies To: Binary search of array problem

#2 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1010
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

Re: Binary search of array problem

Posted 06 July 2013 - 06:43 PM

Something like this should work (it's been a while since I've worked in C++ so any syntax errors are mine)

int StringList::findIndex(string key, int start, int end) {
    if (start > end) return -1;

    int mid = (start + end) / 2;

    if (str[mid].compare(key) > 0) {
        return findIndex(key, start, mid-1);
    } else if (str[mid].compare(key) < 0) {
        return findIndex(key, mid+1, end);
    }

    return mid;
}


This post has been edited by Momerath: 06 July 2013 - 06:44 PM

Was This Post Helpful? 0
  • +
  • -

#3 crodr  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 06-July 13

Re: Binary search of array problem

Posted 06 July 2013 - 07:21 PM

That is the original idea I started with but it didn't work so I had to modify it. I also forgot to mention that when I call findIndex(string key, int start, int end) I pass in the string I am going to add in as key, 0 as start, and ARRAYSIZE-1 as end
Was This Post Helpful? 0
  • +
  • -

#4 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1343
  • View blog
  • Posts: 4,606
  • Joined: 19-February 09

Re: Binary search of array problem

Posted 06 July 2013 - 08:19 PM

Hi, just checking that you remember that the array has to be sorted on the key, for the binary search to work correctly.
Was This Post Helpful? 0
  • +
  • -

#5 crodr  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 06-July 13

Re: Binary search of array problem

Posted 06 July 2013 - 08:22 PM

I'm not sure I follow. So the array has to be sorted before I can do the binary search?
Was This Post Helpful? 0
  • +
  • -

#6 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1343
  • View blog
  • Posts: 4,606
  • Joined: 19-February 09

Re: Binary search of array problem

Posted 06 July 2013 - 08:47 PM

View Postcrodr, on 07 July 2013 - 04:22 AM, said:

I'm not sure I follow. So the array has to be sorted before I can do the binary search?


Yes, it should be pre-sorted if you like.

Binary search algorithm says:

Quote

... a binary search or half-interval search algorithm finds the position of a specified input value (the search "key") within an array sorted by key value...

Was This Post Helpful? 0
  • +
  • -

#7 crodr  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 06-July 13

Re: Binary search of array problem

Posted 06 July 2013 - 08:53 PM

Oh ok. Do you have any suggestions then on how I could input a string into a list bisectionally? This is for a homework assignment that is supposed to show us the speed difference between doing something sequentially vs doing it bisectionally and I don't know how else I could do it. The funny thing is the teacher told me I was on the right path when all I had was the recursion algorithim.
Was This Post Helpful? 0
  • +
  • -

#8 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1343
  • View blog
  • Posts: 4,606
  • Joined: 19-February 09

Re: Binary search of array problem

Posted 06 July 2013 - 09:14 PM

If you are using the function to insert into an array then the array will/should naturally get sorted. If you create an array manually you will need to enter it sorted.

I reckon you will need a loop. Since the array is sorted you divide it in half and check whether the key value is in the lower or upper half. Then you halve that found half and again check which half the key is in, and do that until one position is found.
,

This post has been edited by #define: 06 July 2013 - 09:15 PM

Was This Post Helpful? 0
  • +
  • -

#9 crodr  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 06-July 13

Re: Binary search of array problem

Posted 06 July 2013 - 09:19 PM

I was using the function to find the index where I would insert it but I'll try to implement it now in the function that inserts it into the array. Thank you.
Was This Post Helpful? 0
  • +
  • -

#10 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1343
  • View blog
  • Posts: 4,606
  • Joined: 19-February 09

Re: Binary search of array problem

Posted 06 July 2013 - 09:29 PM

Either way should work, whether your calling function inserts or your find position function inserts.
Was This Post Helpful? 0
  • +
  • -

#11 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Re: Binary search of array problem

Posted 06 July 2013 - 09:39 PM

Just a little 'wrinkle in the works' ...

Does the sorted array allow non-unique values?

Do you always want to insert after the last non-unique value?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1