给出n个元素的排序数组，编写一个函数以搜索数组中给定的元素x

Question

问题解决：给定n个元素的排序数组，编写一个函数以搜索数组中给定元素x。

$查找给定排序数组中的元素。

$查找数字的第一个或最后一个出现。

Answer 1

算法：二进制搜索：

问题解决：给定n个元素的排序数组，编写一个函数以搜索数组中给定元素x。

一种简单的方法是进行线性搜索。以上算法的时间复杂度为O（n）。执行相同任务的另一种方法是使用二进制搜索。

二进制搜索：通过将搜索间隔重复分成两半来搜索排序的数组。从覆盖整个数组的间隔开始。如果搜索键的值小于间隔中间的项目，请将间隔缩小到下半部分。否则将其缩小到上半部分。重复检查，直到找到该值或间隔为空。

...

二进制搜索适用于排序的数组。将该值与数组的中间元素进行比较。如果找不到相等，则消除其中不存在该值的一半。同样，搜索另一半。

二进制搜索的思想是使用对数组进行排序的信息，并将时间复杂度降低到O（Log n）。

在一次比较之后，我们基本上忽略了一半的元素：

1. 将x与中间元素进行比较。
2. 如果x与中间元素匹配，则返回中间索引。
3. 否则，如果x大于中间元素，则x只能位于中间元素之后的右半子数组中。因此，我们重复右半部分。
4. 其他（x较小）重复出现在左半部分。

   public class BinarySearch
   {
    #region helpers.

    /// <summary>
    /// Returns index of x if it is present in int[], else return -1,
    /// </summary>
    /// <param name="array">array of sorted numbers</param>
    /// <param name="l">start index</param>
    /// <param name="r">end index</param>
    /// <param name="x">searched number</param>
    /// <returns>index of x</returns>
    public static int Exist(int[] array, int l, int r, int x)
    {
        while (l <= r)
        {
            int med = (l + r) / 2;
            // Check if x is present at mid
            if (x == array[med])
                return med;
            // If x is smaller, ignore right half
            if (x < array[med])
                r = (med - 1);
            // If x greater, ignore left half
            else
                l = (med + 1);
        }
        return -1;
    }

    /// <summary>
    /// Returns index of first or last occurrence of a number if it is 
        present in int[], else return -1,    
    /// </summary>
    /// <param name="array">array of sorted numbers</param>
    /// <param name="l">start index</param>
    /// <param name="r">end index</param>
    /// <param name="x">searched number</param>
    /// <param name="first">Boolean: true if searching first occurrence 
            or false if last</param>
    /// <returns>index of x</returns>
    public static int Exist(int[] array, int l, int r, int x, bool first)
    {
        int result = -1;
        while (l <= r)
        {
            int med = (l + r) / 2;
            // Check if x is present at mid
            if (x == array[med])
            {
                result = med;
                if (first)
                    r = (med - 1); //ignore right half
                else
                    l = (med + 1); //ignore left half
            }
            else if (x < array[med])
                r = (med - 1);
            else
                l = (med + 1);
        }
        return result;
    }
    #endregion
}
...

class Program
{
    #region props.
    public BinarySearch BinarySearch { get; set; }        
    #endregion
    #region cst.
    public Program()
    {
        this.BinarySearch = new BinarySearch();
    }
    #endregion

    #region publics
    public static void Main()
    {
        //int[] array = { 2, 3, 4, 10, 40 };
        //int count = array.Length - 1;
        //var result = BinarySearch.Exist(array, 0, count, 4); 

        int[] array = { 2, 10, 10, 10, 40 };
        int count = array.Length - 1;
        var result = BinarySearch.Exist(array, 0, count, 40, false);

        Console.WriteLine(result == -1 ? "Element not present" : 
         $"Element 
        found at index {result}");
        Console.ReadKey();                      
    } 
    #endregion
}