Binary search
Increases the ordinal number within 10000-10000 columns, search for the user to enter any number in the range 0 to 9999, find the location of the output of the digital, can't find the return - 1.
C + + language to write the code

CodePudding user response:

Homework do to himself

CodePudding user response:

Seemingly is a data structure, this kind of good do ah,

CodePudding user response:

//-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
///binary search array specified element subscript
/* *
Require an array is an ordered array, and Compare the application of the
@ param [in] paramArray to find array
@ param [in] paramElement to find elements of the
@ param [in] paramEqual compare two elements are equal objects
@ return return search results
- ARRAY_INVALID_INDEX said data not found
- other data value in the array subscript
*/
Template
XInt Array_Find_Binary (const Array & amp; ParamArray, const E & amp; ParamElement, const Compare & amp; ParamCompare)
{
XInt Low=paramArray. GetFirstIndex ();
XInt High=paramArray. GetLastIndex ();
XInt Mid;
XInt iRet=ARRAY_INVALID_INDEX;
While (Low & lt;=High)
{
Mid=+ High (Low)/2;
Const typename Array: : ElementType & amp; Tmp=paramArray (mids);
XInt CompareResult=paramCompare (Tmp, paramElement);
If (CompareResult==0)
{
IRet=Mid;
break;
}
Else if (CompareResult & gt; 0) High=Mid - 1;
The else Low=Mid + 1;
}
Return iRet;
}
This is I wrote so many years ago, this is in the array

CodePudding user response:

Good good study, day day up,

/* binary search from the list of order
Basic idea: in a search range, determined to find the center of the range, use to search for
According to the elements of the key data elements and the center position of the keyword, if both equal lookup into
Work; Otherwise if the former is less than the latter, then the range in the first half of the original search range, continue this
Process; Otherwise if the former is greater than the latter, then the search range of the original search interval, the second half of the
Continue this process. This process has been to find the upper bound of the range is less than the search interval under the
World. Because every time after comparing with the binary search algorithm search interval binary, so the algorithm is also called
Binary search algorithm.

Loop structure of binary search
#include
using namespace std;
Int BiSearch (int a [], int n, int key);
Void main ()
{
Int z;
Int a [10]=,1,2,3,4,5,6,7,8,9 {0}.

Z=BiSearch (a, 10, 4);
cout}

Int BiSearch (int a [], int n, int key)
In order table a [0] - [n - 1) in a binary search key data for the key elements, find success
Returns the element's index number; Failure return 1
{
Int low=0, high=n - 1;
Int mid;
While (low<=high)
{
Mid=+ high (low)/2; Determine the search interval *
If (a/mid==key) return mid; Find success
Else if (a/mid & lt; Low key)=mid + 1;
The else high=mid - 1;
}
return -1; Lookup failure
}


/* the recursive structure of binary search */
#include
using namespace std;
Int BSearch (int a [], int x, int low, int high);
Void main ()
{
Int a []=,3,4,5,17,18,31,33 {1};
Int x=4;
Int bn;
Bn=BSearch (a, x, 0, 7);
If (bn==1) cout<& lt;" X is not in array a!" The else
cout<& lt;" In the array x a subscript is: "& lt; }
Int BSearch (int a [], int x, int low, int high)
{
Int mid;
If (low> High) return 1;//search is not successful
Mid=+ high (low)/2;
If (x==a (mids)) return mid;//find success
Else if (xReturn BSearch (a, x, low, mid - 1);//in the lower half find
The else
Return BSearch (a, x, mid + 1, high);//in sits looking for
}