How do you test this Binary search code? see below HELP!!!?

Question

i was also wondering if you can give me a pseudo-code to explain the algorithm?


public class BinarySearch
{
public static int search(int[ ] list, int key, int first, int last)
{
while (first < last) // Outer loop condition checks if list is finished
{
int mid = (first + last) / 2; // calculate mid(local var) point

if (key < list[mid]) //condition of inner loop if searched number is less than midpoint
{
last = mid; // if so discard other half and set smaller list in last and loop
}
else if (key > list[mid])// enter inner loop if searched number is greater than value searched
{
first = mid + 1; // new starting point coz value is not the same searched for and needs 2 be the next 1
}
else
{
return mid; //found number
}
}
return -1;// NOT_FOUND = -1

}

can you explain how do you test it?

Answer 1

Here's how I see it:

The function searches "list" (which needs to be sequentially arranged, i.e. 1, 2, 3, 4, 6, 9, 12, 50, 52, etc...) for the "key" value starting with the positions "first" and "last". It does a "halving" method where it calculates the point half-way between "first" and "last", stores that value in "mid", and then checks to see what the value is at that point. If "key" is less than the list[mid] value, then it resets "last" to be equal to "mid" because it knows the "key" value comes before the "mid" position. If "key" is greater than the list[mid] value, it sets "first" equal to "mid + 1". It just keeps checking the mid point. If it's lower than "key", it resets the "first" value, if it's higher than "key", it resets the "high" value. If this doesn't make sense I can explain in more detail.

Answer 2

Binary search requires a sorted list. Given an item for which to search, binary search begins by checking the item in the middle of the list. If found, fine; if not, binary search determines which half of the list the item might be in and moves to the center of THAT list. Continue until the item is found or the search is exhausted.

2 4 6 8 10 12 14 16 18 20 22

In searching for 8, binary search will first check 12. 12 is too large, so binary search will next check 6. 6 is too small, so it next checks 10. 10 is too small, but the next check at 8 finds the item.

In searching for 9, binary search checks 12, 6, 10, 8, and returns failure - item not found.

Answer 3

utilising recursion, inorder traversal is easy. only: a million. If there contemporary node has a left subtree, recursively traverse that throughout inorder. 2. pass to the contemporary node, printing, finding out, translating into Swahili, or despite the fact that. 3. If the present node has a best subtree, then recursively traverse that throughout inorder. void inorder_demo(Node *curnode) { cout << '('; // positioned entire undertaking in parentheses if (curnode->left != NULL) inorderdemo(curnode->left); cout << " " << curnode->bribe; if (curNode->best != NULL) inorderdemo(curnode->best); cout << ')'; } Then only initiate the undertaking off with inorder_demo(LocalTree.root). The parentheses are often to grant a seen record of the recursion, additionally they teach the thank you to get an result with the help of including some no longer-strictly-inorder processing. ----Edit: i'm no longer too effective what you asked in extra information. you do no longer could set a subtree node* to NULL to show that this is been visited,...if that's what you're asking. each and each node gets visited only as quickly as, with none marking.