查找与排序02,折半查找

王朝学院·作者佚名  2016-05-17
窄屏简体版  字體: 小  |  中  |  大  |  超大  

查找与排序02,折半查找折半查找,也叫二分查找,当在一个数组或集合中查找某个元素时,先定位出中间位置元素,如果要查找的元素正好和该中间位置元素相等,通过一次查找,就能找到匹配元素;如果要查找的元素小于该中间位置元素,就抛弃后面一半的元素,在前面一半的元素中再定位出中间位置元素,如此反复,直到找到匹配元素;如果要查找的元素大于该中间位置元素,就抛弃前面一半的元素,在后面一半的元素中定位出中间位置元素,如此反复。

面临的第一个问题是:中间位置元素如何定位?在折半查找中规定:当元素个数是奇数,比如有3个元素,中间位置元素是索引为1的元素;当元素个数是偶数,比如有4个元素,索引为1和2的元素理论都是中间位置元素,但在折半查找中,把后面这个,即索引为2的元素视为中间位置元素。

面临的第二个问题是:由于,要查找的元素和中间位置元素之间需要比较,我们在比较之前,势必要让数组按升序或降序来排列。

自定义一个类,该类维护着一个int[]类型数组,通过构造函数确定数组长度和对数组进行排序,并提供打印数组元素的方法,以及折半算法。

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;

 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
© 2005- 王朝網路 版權所有 導航