Databases
StackOverflow2013
Postsdbo
POSomething Wrong with my Binary Search?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSomething Wrong with my Binary Search?
    primarykey
    data
    text
    <p>Here is my attempt at implementing a Binary Search method to look for an arbitrary integer X in an array of 20 and output the number of times it occurs in the array. </p> <p>My output seems to be wrong, as it outputs 1 no matter how many times the given integer appears in the array.</p> <p>Could someone help me out and tell me what's wrong with my code? (I know 20 is quite small and a linear method would be simpler to implement, but I'm using 20 to simplify things)</p> <p>Just to be sure, I'm keying in my input for imin = 0 and imax = 19 I've also made sure I've sorted the array.</p> <pre><code>#include &lt;iostream&gt; #include &lt;cstdlib&gt; #include &lt;vector&gt; using namespace std; int A[20] = {0}; int x; int imin; int imax; int BinarySearch(int A[], int value, int low, int high, int count) { if (high &lt; low){ return -1; // not found } int mid = low + ((high - low) / 2); if (A[mid] &gt; value){ cout&lt;&lt; A[mid] &lt;&lt; " &gt; " &lt;&lt; value &lt;&lt;endl; return BinarySearch(A, value, low, mid-1, count); } else if (A[mid] &lt; value){ cout&lt;&lt; A[mid] &lt;&lt; " &lt; " &lt;&lt; value &lt;&lt;endl; return BinarySearch(A, value, mid+1, high, count); } if (A[mid] == value){ cout&lt;&lt; A[mid] &lt;&lt; " = " &lt;&lt; value &lt;&lt;endl; count = count + 1; } return count; } int main(){ cout&lt;&lt;"Enter 20 integers"&lt;&lt;endl; for (int i = 0; i &lt; 20;i++){ cin&gt;&gt;A[i]; } cout&lt;&lt;"Enter the integer x"&lt;&lt;endl; cin&gt;&gt;x; cout&lt;&lt;"What is imin?"&lt;&lt;endl; cin&gt;&gt;imin; cout&lt;&lt;"What is imax?"&lt;&lt;endl; cin&gt;&gt;imax; int temp; int i; for (int j = 1; j &lt; 20; j++){ i = j - 1; temp = A[j]; while ((i&gt;=0) &amp;&amp; (A[i] &gt; temp) ) { A[i+1] = A[i]; i=i-1; } A[i+1] = temp; } int count = BinarySearch(A, x, imin, imax, 0); cout&lt;&lt;count&lt;&lt;endl; system("pause"); } </code></pre> <p>Thanks so much</p> <p>edit: added in some corrections. but something seems to be wrong with the binary search algorithm i suppose!</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USMatt Ball
    1. USCandy Man
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COYou are not allocating memory for 20 integers.
      singulars
      1. POSomething Wrong with my Binary Search?
      1. USBartek Banachewicz
    2. COHi, apologies! I'm a real greenhorn at this. Could I trouble you to elaborate a little further for me?
      singulars
      1. POSomething Wrong with my Binary Search?
      1. USCandy Man
    3. CO@CandyMan: `int A[] = {0};` <——— that is an array of one element, you read 20 into it. Make it `int A[20] = {0};`.
      singulars
      1. POSomething Wrong with my Binary Search?
      1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload