List of all available Websheets
Viewing cpp/recursion/binary_search by redekopp@usc.edu. You have unsaved changes. Log in above to create, edit, preview and publish Websheets.
Property | Value |
---|---|
Description html markup shown to student | Fill out the method <tt>bsearch(int target, int arr[], int n)</tt> to return -1 if <tt>arr</tt> doesn't contain <tt>target</tt>, and otherwise return <tt>i</tt> where <tt>target == arr[i]</tt>. <p>The <tt>main()</tt>, filled out for you, reads sample cases containing the target, n, and list of numbers in the array. |
Public permissions | |
Remarks Comments, history, license, etc. | Originally by Mark Redekopp (redekopp@usc.edu) and Dave Pritchard (daveagp@gmail.com) |
Engine | |
Template / Reference solution |
using namespace std; int bsearch(int target, int arr[], int n) { // each iteration, // look for 'target' in 'arr[first]..arr[last]' int first = 0; int last = n-1; while (true) { // empty range if (first>last) { return -1; } if (first==last) { // we're done, for better or worse \[ if (target == arr[first]) return first; else return -1; ]\ } int mid = (last+first)/2; // did we find it? if (\[target == arr[mid]]\) { \[return mid;]\ } // continue the search in the appropriate half else if (target > arr[mid]) { \[first = mid+1;]\ } else { \[last = mid-1;]\ } } } int main() { // read target, n, then n sorted inputs int target, n; cin >> target >> n; int* arr = new int[n]; for (int i=0; i<n; i++) cin >> arr[i]; cout << bsearch(target, arr, n); delete [] arr; return 0; } |
C++ test suite json list of stdin/args tests e.g. [{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}] to just run once with no input use [{}] | [ {"stdin": "68\n15\n2 8 15 29 33 34 39 59 60 67 68 80 89 92 98"}, {"stdin": "67\n15\n2 8 15 29 33 34 39 59 60 67 68 80 89 92 98"}, {"stdin": "50\n15\n2 8 15 29 33 34 39 59 60 67 68 80 89 92 98"}, {"stdin": "25\n4\n10 20 30 40"}, {"stdin": "1\n15\n2 8 15 29 33 34 39 59 60 67 68 80 89 92 98"}, {"stdin": "10\n8\n3 8 21 43 78 100 102 105"}, {"stdin": "100\n8\n3 8 21 43 78 100 102 105"}, {"stdin": "1000\n8\n3 8 21 43 78 100 102 105"} ] |
Solution visibility |
Note: problems are open-source by default (see 'Public permissions'). Assumed license for open problems is Creative Commons 4.0 Attribution-ShareAlike unless specified in 'Remarks'.