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, middle1); } else if(checksecondhalf) { return findIndex(key, middle+1, end); } } }
Binary search of array problem
Page 1 of 110 Replies  489 Views  Last Post: 06 July 2013  09:39 PM
#1
Binary search of array problem
Posted 06 July 2013  06:29 PM
Replies To: Binary search of array problem
#2
Re: Binary search of array problem
Posted 06 July 2013  06:43 PM
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, mid1); } 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
#3
Re: Binary search of array problem
Posted 06 July 2013  07:21 PM
#4
Re: Binary search of array problem
Posted 06 July 2013  08:19 PM
#5
Re: Binary search of array problem
Posted 06 July 2013  08:22 PM
#6
Re: Binary search of array problem
Posted 06 July 2013  08:47 PM
crodr, on 07 July 2013  04:22 AM, said:
Yes, it should be presorted if you like.
Binary search algorithm says:
Quote
#7
Re: Binary search of array problem
Posted 06 July 2013  08:53 PM
#8
Re: Binary search of array problem
Posted 06 July 2013  09:14 PM
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
#9
Re: Binary search of array problem
Posted 06 July 2013  09:19 PM
#10
Re: Binary search of array problem
Posted 06 July 2013  09:29 PM
#11
Re: Binary search of array problem
Posted 06 July 2013  09:39 PM
Does the sorted array allow nonunique values?
Do you always want to insert after the last nonunique value?
