int binsearch(int list[], int searchnum, int left, int right) { int middle; while (left <= right) { middle = (left + right) / 2; if (list[middle] < searchnum) { left = middle + 1; } else if (list[middle] == searchnum) { return middle; } else { right = middle - 1; } } return -1; } int binSearchRecurse(int list[], int searchnum, int left, int right) { int middle; while (left < right) { middle = (left + right) / 2; if (list[middle] < searchnum) { binSearchRecurse(list, searchnum, middle + 1, right); break; } else if (list[middle] == searchnum) { return middle; break; } else { binSearchRecurse(list, searchnum, left, middle - 1); break; } } }

These are functions.

 int seqSearch(int[], int, int); int main() { int i, j, position; int list[MAX_SIZE]; int sizeList[] = {0,10,20,30,40,50,60,70,80,90,100,200,400,600,800,1000}; int numTimes[] = {30000,12000,6000,5000,4000,4000,4000,3000,3000,2000,2000,1000,500,500,500,200}; clock_t start, stop; double duration, total; for (i = 0; i < MAX_SIZE; i++) list[i] = i; for (i = 0; i < ITERATIONS; i++) { start = clock(); for (j = 0; j < numTimes[i]; j++) { position = seqSearch(list, -1, sizeList[i]); } stop = clock(); total = ((double)(stop - start)); duration = total / numTimes[i]; cout << sizeList[i] << " " << numTimes[i] << " " << (int)(stop - start) << " " << total << " " << duration << endl; list[sizeList[i]] = sizeList[i]; } system("pause"); getchar(); return 0; } int seqSearch(int arr[], int n, int x) { int i; for (i = 0; i < n; i++) { if (arr[i] == x) return i; } return -1; }

Through this, it is necessary to determine the worst case performance and the average time of the binary algorithm. For me, this new account for such things, who can help. Thank.

    1 answer 1

    For binary search in both cases, the performance in the worst case is O(log n) , for sequential ( seqSearch ) - O(n) .

    This is if you are interested in the answer. If you are interested in how to count this, then take almost any book on algorithms. Very briefly - a binary search halves the whole range, so for a length of 2 k it is necessary to make k divisions, or for a range of length n - about log n divisions. The check is performed in constant time.

    For the consecutive in the worst case, one must go through all n elements.

    In the best case, you and there, and there you get to the desired element immediately, - total O(1) , on average - also O(log n) for the binary, O(n) for the sequential one.

    • and what is the code used in main ()? - arman
    • As I understand it, to perform timing and plotting, in practice, proving the conclusions made about the performance of algorithms. - Harry
    • thank you very much. - arman