c# 二分查找算法

折半搜索，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。

A 搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；

B 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

C 如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

时间复杂度折半搜索每次把搜索区域减少一半，时间复杂度为。

（n代表集合中元素的个数）空间复杂度

代码如下:

/// <summary>
/// 二分查找
/// </summary>
/// <param name="arr"></param>
/// <param name="low">开始索引 0</param>
/// <param name="high">结束索引 </param>
/// <param name="key">要查找的对象</param>
/// <returns></returns>
public static int BinarySearch(int[] arr, int low, int high, int key)
{
    int mid = (low + high) / 2;
    if (low > high)
        return -1;
    else
    {
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] > key)
            return BinarySearch(arr, low, mid - 1, key);
        else
            return BinarySearch(arr, mid + 1, high, key);
    }
}

实例：

代码如下:

int[] y = new int[] {1,2,3,4,5,6,7,8,9,10,11,12,13 };
int rr = BinarySearch(y, 0, y.Length - 1, 13);
Console.Write(rr);    //12

赞 (0)

相关推荐

  • C#查找字符串所有排列组合的方法

    本文实例讲述了C#查找字符串所有排列组合的方法.分享给大家供大家参考.具体实现方法如下: // 1. remove first char // 2. find permutations of the rest of chars // 3. Attach the first char to each of those permutations. // 3.1 for each permutation, move firstChar in all indexes // to produce even

  • C# 数组查找与排序实现代码

    1. 查找对象 复制代码 代码如下: Person p1 = new Person( " http://www.my400800.cn " , 18 ); Person p2 = new Person( " http://www.my400800.cn " , 19 ); Person p3 = new Person( " http://www.my400800.cn " , 20 ); Person[] persons = ... { p1,

  • C# 递归查找树状目录实现方法

    1.递归查找树状目录 复制代码 代码如下: public partial class Form1 : Form    {        string path = @"F:\学习文件";//递归查找树状目录        public Form1()        {递归查找树状目录            InitializeComponent();        }        private void Form1_Load(object sender, EventArgs e) 

  • C#中怎样从指定字符串中查找并替换字符串?

    C#中怎样从指定字符串中查找并替换字符串?

    using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Linq;using System.Text;using System.Windows.Forms;#region             #endregionnamespace Find{    public partial class Form

  • C#几种截取字符串的方法小结

    1.根据单个分隔字符用split截取 例如 复制代码 代码如下: string st="GT123_1"; string[] sArray=st.split("_"); 即可得到sArray[0]="GT123",sArray[1]="1"; 2.利用多个字符来分隔字符串 例如 复制代码 代码如下: string str = "GTAZB_JiangjBen_123";string[] sArray = s

  • C#使用二分查找法判断指定字符的方法

    本文实例讲述了C#使用二分查找法判断指定字符的方法.分享给大家供大家参考,具体如下: private int sort_init(ref string[] chars, string str) //数组初始化 { string[] temp = str.Split(' '); //temp. chars = new string[temp.Count()]; int ndx = 0; int last_empty_positon = 0; foreach (string ch in temp)

  • C#中查找Dictionary中重复值的方法

    简介 在这篇帮助文档中,我将向你展示如何实现c#里字典中重复值的查找.你知道的对于一个老鸟来说,这是非常简单的代码.但是尽管如此,这也是一篇对c#初学者非常有用的帮助文档. 背景 多数程序员对小型数据源存储的处理方式通常是创建字典进行键值存储.主键时唯一的,但是字典值却可能有重复的元素. 代码 这里我使用了一个简单的LINQ语句来查找字典中的重复值. 复制代码 代码如下: //initialize a dictionary with keys and values.    Dictionary<

  • C#二分查找算法实例分析

    本文实例讲述了C#二分查找算法.分享给大家供大家参考.具体实现方法如下: // input array is assumed to be sorted public int BinarySearch(int[] arr, int x) { if (arr.Length == 0) return -1; int mid = arr.Length / 2; if (arr[mid] == x) return mid; if (x < arr[mid]) return BinarySearch(Get

  • c#实现16进制和字符串之间转换的代码

    十六进制字符串与数值类型之间转换(C# 编程指南) 以下示例演示如何执行下列任务: 获取字符串中每个字符的十六进制值. 获取与十六进制字符串中的每个值对应的字符. 将十六进制 string 转换为整型. 将十六进制 string 转换为浮点型. 将字节数组转换为十六进制 string. 示例 此示例输出 string 中的每个字符的十六进制值.首先,它将 string 分析为字符数组,然后对每个字符调用 ToInt32(Char) 以获取相应的数字值.最后,在 string 中将数字的格式设置为

  • c#字符串查找某词出现的次数及索引

    字符串方法的使用: indexof(): 有9个重载,具体的请转到F12查看详细内容: 本文使用的是第6个重载: 如果找到该字符串,则为从零开始的索引位置:如果未找到该字符串,则为 -1 有两个参数: string value:要搜索的字符 int startIndex:搜索的起始位置 复制代码 代码如下: class Program    {        static void Main(string[] args)        {            //统计出字符串中,下雪出现的次数

随机推荐