计算二分查找的比较次数
Count number of comparisons for a binary search
我希望能够计算二进制搜索在我的代码中进行比较的次数。基本上，我正在处理的程序输出一个未排序的数组，然后用户输入一个数字，它在数组中找到这个数字，然后吐出它所做的比较次数（气泡交换）和它所在的索引。然后它吐出排序后的数组并要求用户输入另一个数字。
问题：我似乎无法弄清楚如何计算二分查找必须进行的比较次数，以确定该数字是否在数字列表中。
代码：
class Lab3
{
static int[] intArray = {17, 166, 288, 324, 531, 792, 946, 157, 276, 441, 533, 355, 228, 879, 100, 421, 23, 490, 259, 227,
216, 317, 161, 4, 352, 463, 420, 513, 194, 299, 25, 32, 11, 943, 748, 336, 973, 483, 897, 396,
10, 42, 334, 744, 945, 97, 47, 835, 269, 480, 651, 725, 953, 677, 112, 265, 28, 358, 119, 784,
220, 62, 216, 364, 256, 117, 867, 968, 749, 586, 371, 221, 437, 374, 575, 669, 354, 678, 314, 450,
808, 182, 138, 360, 585, 970, 787, 3, 889, 418, 191, 36, 193, 629, 295, 840, 339, 181, 230, 150 };
static void Main(string[] args)
{
// Prints unsorted array
PrintArray(intArray);
// Gets user input and then checks if it's inside the array, if not it outputs that it isn't, that's all this does.
SearchIntArray(intArray);
// Bubble swap kicks in and sorts the array
BubbleSort(intArray);
// Binary Search kicks in and searches for the second user input to see if it's in the array and gives the index that it's at.
BinarySearch(intArray);
}
// This checks to see whether or not the int entered by the user is actually in the array, pretty straightforward stuff
static int SearchIntArray(int[] intArray)
{
// get user input to check array for number
Console.Write("Enter an integer: ");
int guess = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("The number you entered is " + guess);
// sort through array to find the number entered by the user
int index = 0;
int numOfSwaps = 0;
while (index < intArray.Length && guess != intArray[index])
{
index++;
}
numOfSwaps = index;
if (index >= intArray.Length)
Console.Write("Made 100 comparions, the number " + guess + " was not found in the unsorted array");
else Console.Write("Made " + (numOfSwaps+1) + " comparisons to find " + guess + " is at index " + index + " in the unsorted array");
//Adds blank lines
Console.WriteLine();
Console.WriteLine();
Console.Write("Number of comparisons: 4884");
// adds blank lines
Console.WriteLine();
int niddleIndex = -1;
return niddleIndex;
}
static int BubbleSort(int[] arr)
{
int numOfSwaps = 0;
// Bubble swap kicks in and sorts the array
Console.WriteLine("The sorted array: ");
int temp = 0;
for (int write = 0; write < intArray.Length; write++)
{
for (int sort = 0; sort < intArray.Length - 1; sort++)
{
if (intArray[sort] > intArray[sort + 1])
{
temp = intArray[sort + 1];
intArray[sort + 1] = intArray[sort];
intArray[sort] = temp;
}
}
}
for (int i = 0; i < intArray.Length; i++)
Console.Write(intArray[i] + ", ");
//Adds a blank line
Console.WriteLine();
Console.WriteLine();
Console.WriteLine("In total, swapped 2344 times to sort this array");
//Adds a blank line
Console.WriteLine();
return numOfSwaps;
}
static int BinarySearch(int[] intArray)
{
int x = 101;
// parses the user input into the int secondInputParsed
Console.Write("Enter an integer: ");
Console.WriteLine();
string secondInput = Console.ReadLine();
int secondInputParsed = Int32.Parse(secondInput);
int low = 0;
int high = x - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (secondInputParsed < intArray[mid])
high = mid - 1;
else if (secondInputParsed > intArray[mid])
low = mid + 1;
else if (secondInputParsed == intArray[mid])
{
// Only problem I'm having is to get the number of searches for the binary search, just that, everything else works good!
Console.WriteLine();
Console.WriteLine("Made " + low + " comparisons to find {0} is at index {1} in the sorted array, using Binary Search", secondInputParsed, mid);
Console.WriteLine();
Console.WriteLine("Press anything to exit the program");
Console.ReadLine();
return -1;
}
}
Console.WriteLine("Made 7 comparisons to find " + secondInput + " is not in the sorted array, using Binary Search");
Console.WriteLine();
Console.WriteLine("Press anything to exit the program");
Console.ReadLine();
return -1;
}
//call this method to print an integer array to the console.
static void PrintArray(int[] arr)
{
Console.WriteLine("The unsorted array: ");
for (int i = 0; i < arr.Length; i++)
{
if (i != arr.Length - 1)
{
Console.Write("{0}, ", arr[i]);
}
else
{
Console.Write("{0} ", arr[i]);
}
}
// These create 2 blank lines between the printArray and to get the user input. Makes it look nicer, that's all.
Console.WriteLine();
Console.WriteLine();
}
}
}
您得到了不同的结果，因为您的变体在某些情况下运行速度稍快。二进制搜索取决于您如何拆分数据（即，如果您有 7 个元素，第一组可能是 3 或 4 个元素，在这里您可能或多或少是幸运的）。但是，您从 high 的错误值开始，这可能会导致异常（尝试在您的程序中输入 1500）。该数组有 100 个元素，但它们的编号是从 0 到 99，而不是从 1 到 100。如果你从 low = 0 和 hight = 100 开始，你的数组必须有 101 个元素！如果 high 错误，您会计算出错误的 mid，然后比算法的经典版本更幸运，shell 看起来像这样：
int low = 0;
int high = intArray.Length - 1;
var count = 0;
while (low <= high)
{
count++;
int mid = (low + high) / 2;
if (secondInputParsed < intArray[mid])
high = mid - 1;
else if (secondInputParsed > intArray[mid])
low = mid + 1;
else
{
Console.WriteLine();
Console.WriteLine("Made {2} comparisons to find {0} is at index {1} in the sorted array, using Binary Search", secondInputParsed, mid, count);
...
}
}
Console.WriteLine("Made {0} comparisons to find {1} is not in the sorted array, using Binary Search", count, secondInput);
我希望能够计算二进制搜索在我的代码中进行比较的次数。基本上，我正在处理的程序输出一个未排序的数组，然后用户输入一个数字，它在数组中找到这个数字，然后吐出它所做的比较次数（气泡交换）和它所在的索引。然后它吐出排序后的数组并要求用户输入另一个数字。
问题：我似乎无法弄清楚如何计算二分查找必须进行的比较次数，以确定该数字是否在数字列表中。
代码：
class Lab3
{
static int[] intArray = {17, 166, 288, 324, 531, 792, 946, 157, 276, 441, 533, 355, 228, 879, 100, 421, 23, 490, 259, 227,
216, 317, 161, 4, 352, 463, 420, 513, 194, 299, 25, 32, 11, 943, 748, 336, 973, 483, 897, 396,
10, 42, 334, 744, 945, 97, 47, 835, 269, 480, 651, 725, 953, 677, 112, 265, 28, 358, 119, 784,
220, 62, 216, 364, 256, 117, 867, 968, 749, 586, 371, 221, 437, 374, 575, 669, 354, 678, 314, 450,
808, 182, 138, 360, 585, 970, 787, 3, 889, 418, 191, 36, 193, 629, 295, 840, 339, 181, 230, 150 };
static void Main(string[] args)
{
// Prints unsorted array
PrintArray(intArray);
// Gets user input and then checks if it's inside the array, if not it outputs that it isn't, that's all this does.
SearchIntArray(intArray);
// Bubble swap kicks in and sorts the array
BubbleSort(intArray);
// Binary Search kicks in and searches for the second user input to see if it's in the array and gives the index that it's at.
BinarySearch(intArray);
}
// This checks to see whether or not the int entered by the user is actually in the array, pretty straightforward stuff
static int SearchIntArray(int[] intArray)
{
// get user input to check array for number
Console.Write("Enter an integer: ");
int guess = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("The number you entered is " + guess);
// sort through array to find the number entered by the user
int index = 0;
int numOfSwaps = 0;
while (index < intArray.Length && guess != intArray[index])
{
index++;
}
numOfSwaps = index;
if (index >= intArray.Length)
Console.Write("Made 100 comparions, the number " + guess + " was not found in the unsorted array");
else Console.Write("Made " + (numOfSwaps+1) + " comparisons to find " + guess + " is at index " + index + " in the unsorted array");
//Adds blank lines
Console.WriteLine();
Console.WriteLine();
Console.Write("Number of comparisons: 4884");
// adds blank lines
Console.WriteLine();
int niddleIndex = -1;
return niddleIndex;
}
static int BubbleSort(int[] arr)
{
int numOfSwaps = 0;
// Bubble swap kicks in and sorts the array
Console.WriteLine("The sorted array: ");
int temp = 0;
for (int write = 0; write < intArray.Length; write++)
{
for (int sort = 0; sort < intArray.Length - 1; sort++)
{
if (intArray[sort] > intArray[sort + 1])
{
temp = intArray[sort + 1];
intArray[sort + 1] = intArray[sort];
intArray[sort] = temp;
}
}
}
for (int i = 0; i < intArray.Length; i++)
Console.Write(intArray[i] + ", ");
//Adds a blank line
Console.WriteLine();
Console.WriteLine();
Console.WriteLine("In total, swapped 2344 times to sort this array");
//Adds a blank line
Console.WriteLine();
return numOfSwaps;
}
static int BinarySearch(int[] intArray)
{
int x = 101;
// parses the user input into the int secondInputParsed
Console.Write("Enter an integer: ");
Console.WriteLine();
string secondInput = Console.ReadLine();
int secondInputParsed = Int32.Parse(secondInput);
int low = 0;
int high = x - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (secondInputParsed < intArray[mid])
high = mid - 1;
else if (secondInputParsed > intArray[mid])
low = mid + 1;
else if (secondInputParsed == intArray[mid])
{
// Only problem I'm having is to get the number of searches for the binary search, just that, everything else works good!
Console.WriteLine();
Console.WriteLine("Made " + low + " comparisons to find {0} is at index {1} in the sorted array, using Binary Search", secondInputParsed, mid);
Console.WriteLine();
Console.WriteLine("Press anything to exit the program");
Console.ReadLine();
return -1;
}
}
Console.WriteLine("Made 7 comparisons to find " + secondInput + " is not in the sorted array, using Binary Search");
Console.WriteLine();
Console.WriteLine("Press anything to exit the program");
Console.ReadLine();
return -1;
}
//call this method to print an integer array to the console.
static void PrintArray(int[] arr)
{
Console.WriteLine("The unsorted array: ");
for (int i = 0; i < arr.Length; i++)
{
if (i != arr.Length - 1)
{
Console.Write("{0}, ", arr[i]);
}
else
{
Console.Write("{0} ", arr[i]);
}
}
// These create 2 blank lines between the printArray and to get the user input. Makes it look nicer, that's all.
Console.WriteLine();
Console.WriteLine();
}
}
}
您得到了不同的结果，因为您的变体在某些情况下运行速度稍快。二进制搜索取决于您如何拆分数据（即，如果您有 7 个元素，第一组可能是 3 或 4 个元素，在这里您可能或多或少是幸运的）。但是，您从 high 的错误值开始，这可能会导致异常（尝试在您的程序中输入 1500）。该数组有 100 个元素，但它们的编号是从 0 到 99，而不是从 1 到 100。如果你从 low = 0 和 hight = 100 开始，你的数组必须有 101 个元素！如果 high 错误，您会计算出错误的 mid，然后比算法的经典版本更幸运，shell 看起来像这样：
int low = 0;
int high = intArray.Length - 1;
var count = 0;
while (low <= high)
{
count++;
int mid = (low + high) / 2;
if (secondInputParsed < intArray[mid])
high = mid - 1;
else if (secondInputParsed > intArray[mid])
low = mid + 1;
else
{
Console.WriteLine();
Console.WriteLine("Made {2} comparisons to find {0} is at index {1} in the sorted array, using Binary Search", secondInputParsed, mid, count);
...
}
}
Console.WriteLine("Made {0} comparisons to find {1} is not in the sorted array, using Binary Search", count, secondInput);