1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

public class MyArray

{

    private int[] arr;//内部维护着一个数组

    private static Random r = new Random();//用它来生成数组的随机元素

    //通过构造函数来确定内部数组的长度，并生成数组的随机元素,并对数组元素排序

    public MyArray(int size)

    {

        arr = new int[size];

        for (int i = 0; i < size; i++)

        {

            arr[i] = r.Next(1, 100);

        }

        Array.Sort(arr);

    }

    //折半查找算法 返回查找元素的索引位置

    public int HalfSearch(int key)

    {

        int low = 0;//低点，初始值设置成最低点，即索引0

        int high = arr.Length - 1;//高点，初始值设置成最高点，即索引数组最后一个位置

        //如果数组元素个数是偶数，比如4个，索引2和3都是中间位置，用以下算法中间位置指向索引3

        //如果数组元素个数是奇数，比如3个，索引1是中间位置，用以下算法中间位置指向索引1

        int middle = (low + high + 1)/2;

        int location = -1;//找不到就返回-1

        //循环，找不到就一直查找

        do

        {

            //每次循环，把低点和高点位置的元素打印出来

            Console.WriteLine(PrintSectionElements(low, high));

            Console.WriteLine();

            //如果要查找元素是中间位置的元素，就返回中间位置这个索引

            if (key == arr[middle])

            {

                location = middle;

            }

            else if (key < arr[middle]) //如果要查找元素小于中间位置元素，把中间位置前面的索引设为高点

            {

                high = middle - 1;

            }

            else//如果要查找元素大于中间位置元素，把中间位置后面的索引设为低点

            {

                low = middle + 1;

            }

            //如果代码运行到此处，说明还没有找到匹配元素，由于以上重新设置了低点或高点，所以这里也要重新设置中间位置

            middle = (low + high + 1)/2;

        } while ((low <= high) && (location == -1));

        return location;

    }

    //打印2个位置间的数组元素

    public string PrintSectionElements(int low, int high)

    {

        string temp = "";

        //对于2个位置间的元素打印出元素并跟上一个空格位置

        for (int i = low; i <= high; i++)

        {

            temp += arr[i] + " ";

        }

        return temp;

    }

    //重写ToString方法，把数组所有的元素都打印出来

    public override string ToString()

    {

        return PrintSectionElements(0, arr.Length - 1);

    }

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

class Program

{

    private static int key; //需查找元素

    private static int position;//匹配元素所在的位置

    static void Main(string[] args)

    {

        MyArray myArray = new MyArray(7);

        //把所有元素打印出来

        Console.WriteLine(myArray);

        Console.WriteLine("请输入需要查找的元素或输入-1退出 ");

        key = Convert.ToInt32(Console.ReadLine());

        Console.WriteLine();

        while (key != -1)

        {

            //调用折半算法得出所需查找元素的位置

            position = myArray.HalfSearch(key);

            if (position == -1) //说明没有找到需要匹配的元素

            {

                Console.WriteLine("没有找到元素{0}", key);

            }

            else

            {

                Console.WriteLine("在{0}号位置查到元素{1}", position, key);

            }

            Console.WriteLine("请输入需要查找的元素或输入-1退出 ");

            key = Convert.ToInt32(Console.ReadLine());

            Console.WriteLine();

        }

    }

}