Hi profissional teams, I have this example regarding the Binary search need to be clarified
Thank you for your assistant
+++++++++++++++++++++++++++++++++++
static void Main(string[] args)
{
int[] arrayList = { 45, 36, 77, 12, -98, 0, 6, 22, 32, -3 };
int[] sortedArrayList = { -98, -3, 0, 6, 12, 22, 32, 36, 45, 77};
int[] searchElement = { 45, -3, 12, 102, -102, 15 };
int position, i;
for (int pos = 0; pos < searchElement.Length; pos++)
{
position = LinearSearch(arrayList, searchElement[pos], out i);
if (position == -1)
Console.WriteLine("{0} is not in ArrayList.{1}", searchElement[pos], i);
else
Console.WriteLine("{0} is at position {1} in ArrayList", searchElement[pos],
position);
}
for (int pos = 0; pos < searchElement.Length; pos++)
{
position = BetterLinearSearch(sortedArrayList, searchElement[pos], out i);
if (position == -1)
Console.WriteLine("{0} is not in sortedArrayList.{1}", searchElement[pos], i);
else
Console.WriteLine("{0} is at position {1} in sortedArrayList", searchElement[pos],
position);
}
}
// BinarySearch method
static int MyBinarySearch(int[] keys, int v) {
int position = -1;
int begin = 0, end = keys.Length - 1;
bool found = false;
while ((begin <= end) && !found) {
position = (begin + end) / 2;
if (keys[position] == v)
found = true; // just right
else if (keys[position] < v)
begin = position + 1; // too small
else
end = position - 1; // too big
}
if (found)
return position;
else
return -1;
}
AlanPosted Feb 12, 2008, 5:36 AM
Well, the binary search technique assumes that the array has already been sorted - into ascending order in the case of the code you posted.
First of all you start with the middle element (or one less than the middle element if there are an even number of elements). If that element is the one you're searching for then the job's done.
Otherwise, if what you're searching for is less than the middle element, then you know that (if it's there at all) it must be in the first half of the elements in the array. Similarly, if what you're seaching for is more than the middle element, then it must be in the second half of the elements in the array.
You therefore do another binary search on the first or second halves of the array (as the case may be) and carry on like this until you eventually find the element you're looking for or discover it's not present.
It's therefore a technique which successively reduces the elements to search over (reducing them by about a half each time) until a result is obtained. This is achieved in the code you posted by manipulating the beginning and end indices ( the variables 'begin' and 'end') to obtain the segment of the array to be seached next.