采用二分查找法从一个已经升序排序的数组a[n]中,查找某个数k。如果找到k, 输出k所在的数组下标(0~n-1)及比较次数。若x不存在,输出-1和比较次数。
如:
数组a[n]:3 5 6 7 9
采用二分查找法查找5,则:
第一次比较:6
第二次比较:3
第三次比较:5
则经过3次比较,查找到5,输出数组下标:1
查找4时,则
第一次比较:6
第二次比较:3
第三次比较:5
则经过3次比较后,未找到4,输出-1。
采用二分查找法从一个已经升序排序的数组a[n]中,查找某个数k。如果找到k, 输出k所在的数组下标(0~n-1)及比较次数。若x不存在,输出-1和比较次数。
如:
数组a[n]:3 5 6 7 9
采用二分查找法查找5,则:
第一次比较:6
第二次比较:3
第三次比较:5
则经过3次比较,查找到5,输出数组下标:1
查找4时,则
第一次比较:6
第二次比较:3
第三次比较:5
则经过3次比较后,未找到4,输出-1。
望采纳! 谢谢
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace BinarySearch
{
class Program
{
static Random random = new Random();
static int[] RandArray(int len = 10)
{
int[] array = new int[len];
for (int i = 0; i < len; i++)
{
int r = random.Next(0, 10);
array[i] = r;
}
return array;
}
static void PrintArray(int[] array)
{
for (int i = 0; i < array.Length; i++)
{
Console.Write(array[i] + " ");
}
Console.WriteLine();
}
static void BubbleSort(int[] array)
{
for (int i = 0; i < array.Length - 1; i++)
{
bool swapped = false;
for (int j = 0; j < array.Length - i - 1; j++)
{
if (array[j] > array[j + 1])
{
int box;
box = array[j];
array[j] = array[j + 1];
array[j + 1] = box;
swapped = true;
}
}
if (!swapped)
{
break;
}
}
}
//若有重复数字返回的值是随机一个
static int BinarySearch(int[] array,int num)
{
int start = 0;
int end = array.Length;
while (start < end)
{
int n = (start + end) / 2;
if (array[n] == num)
{
return n + 1;
}
else if (array[n] > num)
{
end = n;
}
else
{
start = n + 1;
}
}
return -1;
}
static void Main(string[] args)
{
int[] array = RandArray();
PrintArray(array);
BubbleSort(array);
PrintArray(array);
int num = int.Parse(Console.ReadLine());
if (BinarySearch(array, num) == -1)
{
Console.WriteLine("数组中不存在数字{0}", num);
}
else
{
Console.WriteLine("查找的数字在数组中第{0}个", BinarySearch(array, num));
}
Console.ReadLine();
}
}
}