计算机算法设计与分析(第3版)课后习题答案算法分析题2-3(p38)设a[0:n-1]是已排好序的数组。改写二分搜索算法,是得当搜索元素x不在数组中时,返回小于x的最大元素位置i和大于X的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace finddata
{
class Program
{
static int _BinarySearch(int[] arr, int N_search)
{
int len = arr.Length;
int left = 0;
int right = len - 1;
if (len > 0 && N_search >= arr[0])
{
while (left < right)
{
int middle = (left + right + 1) / 2;
if (N_search < arr[middle])
{
right = middle - 1;
}
else
{
left = middle;
}
}
if (N_search == arr[left])
return left;
}
return -1;
}

static void Main(string[] args)
{
int[] inputlist = new int[5];//接收用户输入的数组
int position;
int[] templist = new int[6];
int num;
Console.WriteLine("\n请向数组输入5个数（输入回车换行；回车结束输入）：");
for (int i = 0; i < inputlist.Length; i++)
{
inputlist[i] = Convert.ToInt32(Console.ReadLine());
}//接收一个数组
for (; ; )
{
Console.Write("\n请输入一个需要查询的数：");
num = Convert.ToInt32(Console.ReadLine());//获取要查询的数据

int f = _BinarySearch(inputlist, num);

//在数组数据范围内，判断是否是数组一员
if (f != -1)
{
Console.WriteLine("\n" + num + "位于数组(位置是1~5)的第：{0}位", f + 1);
}
else
{
ArrayList arrylist = new ArrayList(inputlist);//建一个动态数组
arrylist.Add(num);
arrylist.Sort();
for (int i = 0; i < arrylist.Count; i++)
{
templist[i] = Convert.ToInt32(arrylist[i]);
}
position = _BinarySearch(templist, num);
if (position == 0 )
{
Console.WriteLine("\n{0}（min）<[数组最小元素：{1}]。位置：数组元素（位置1~5）第[{2}]之前！", num,templist[position +1], position +1);
}
else if (position == templist.Leng
th-1)
{
Console.WriteLine("\n{0}（max）>[数组最大元素：{1}]。位置：数组元素（位置1~5）第[{2}]之后！", num, templist[position-1], position );
}
else
{

计算机算法设计与分析(第3版)课后习题答案算法分析题2-3(p38)设a[0:n-1]是已排好序的数组。改写二分搜索算法,是得当搜索元素x不在数组中时,返回小于x的最大元素位置i和大于X的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。

Console.WriteLine("\n位于数组元素：[{0},{1}]之间。位置：（位置1~5）即第[{2}]与第[{3}]之间！", templist[position - 1], templist[position + 1], position, position + 1);
}
}
}
}
}
}