百度面试题：求绝对值最小的数

参考了这篇博客的内容和思路：http://www.cnblogs.com/nokiaguy/archive/2013/01/29/2881476.html

有一个已经排序的数组（升序），数组中可能有正数、负数或0，求数组中元素的绝对值最小的数，要求，不能用顺序比较的方法（复杂度需要小于O（n）），可以使用任何语言实现

例如，数组{-20，-13，-4, 6, 77,200} ，绝对值最小的是-4。

算法实现的基本思路

三种情况：
全负数 全正数 正负皆有
1：取最右 时间复杂度为o(1)
2：取最左 时间复杂度为o(1)
3：二分查找0， 找到为最小，否则最后查找区间，左右取绝对值最小，时间复杂度为o(log2 n)

     解法一：

View Code 
      private static IEnumerable<int> GetABSMinValue1(IList<int> arr)
         {
             var ret = new List<int>();
             if (arr.Count < 2)
             {
                 ret.Add(arr[0]);
             }
             else
             {
                 if (arr[arr.Count - 1] <= 0)
                 {
                     ret.Add(arr[arr.Count - 1]);
                 }
                 else if (arr[0] >= 0)
                 {
                     ret.Add(arr[0]);
                 }
                 else
                 {
                     //方法一：循环遍历法
                     for (int i = 0; i < arr.Count; i++)
                     {
                         if (arr[i] < 0 && arr[i + 1] >= 0)
                         {
                             if (Math.Abs(arr[i]) > Math.Abs(arr[i + 1]))
                             {
                                 ret.Add(arr[i + 1]);
                             }
                             else if (Math.Abs(arr[i]) < Math.Abs(arr[i + 1]))
                             {
                                 ret.Add(arr[i]);
                             }
                             else
                             {
                                 ret.Add(arr[i]);
                                 ret.Add(arr[i + 1]);
                             }
                         }
                     }
                 }
             }
 
             return ret;
         }

　　解法二：

View Code 
         private static IEnumerable<int> GetABSMinValue2(IList<int> arr)
         {
             var ret = new List<int>();
             if (arr.Count < 2)
             {
                 ret.Add(arr[0]);
             }
             else
             {
                 if (arr[arr.Count - 1] <= 0)
                 {
                     ret.Add(arr[arr.Count - 1]);
                 }
                 else if (arr[0] >= 0)
                 {
                     ret.Add(arr[0]);
                 }
                 else
                 {
                     //方法二：第一步是二分法，第二步循环遍历法
                     int low = 0, high = arr.Count - 1, mid;
                     while (low <= high)
                     {
                         mid = (low + high) / 2;
                         if (arr[mid] == 0)
                             ret.Add(arr[mid]);
                         if (arr[mid] > 0) //中间位置为正数
                         {
                             if (arr[mid - 1] < 0) //中间位置前一个为负数
                             {
                                 if (Math.Abs(arr[mid - 1]) == arr[mid])
                                 {
                                     ret.Add(arr[mid - 1]);
                                     ret.Add(arr[mid]);
                                 }
                                 else
                                 {
                                     ret.Add(Math.Abs(arr[mid - 1]) > arr[mid] ? arr[mid] : arr[mid - 1]);
                                 }
                                 break;
                             }
                             high = mid - 1;
                         }
                         else //中间位置为负数
                         {
                             if (arr[mid + 1] > 0) //中间位置后一个为正数
                             {
                                 if (Math.Abs(arr[mid]) == arr[mid + 1])
                                 {
                                     ret.Add(arr[mid]);
                                     ret.Add(arr[mid + 1]);
                                 }
                                 else
                                 {
                                     ret.Add(Math.Abs(arr[mid]) > arr[mid + 1] ? arr[mid + 1] : arr[mid]);
                                 }
                                 break;
                             }
                             low = mid + 1;
                         }
                     }
                 }
             }
 
             return ret;
         }

　　解法三：

View Code 
         private static void binarySearch(int low, int high, IList<int> arr, ref List<int> ret)
         {
             while (low <= high)
             {
                 int mid = (low + high) / 2;
                 if (arr[mid] == 0)
                 {
                     ret.Add(arr[mid]);
                     break;
                 }
                 if (arr[mid] > 0) //中间位置为正数
                 {
                     if (arr[mid - 1] < 0) //中间位置前一个为负数
                     {
                         if (Math.Abs(arr[mid - 1]) == arr[mid])
                         {
                             ret.Add(arr[mid - 1]);
                             ret.Add(arr[mid]);
                         }
                         else
                         {
                             ret.Add(Math.Abs(arr[mid - 1]) > arr[mid] ? arr[mid] : arr[mid - 1]);
                         }
                         break;
                     }
                     high = mid - 1;
                     binarySearch(low, high, arr, ref ret);
                     break;
                 }
                 else //中间位置为负数
                 {
                     if (arr[mid + 1] > 0) //中间位置后一个为正数
                     {
                         if (Math.Abs(arr[mid]) == arr[mid + 1])
                         {
                             ret.Add(arr[mid]);
                             ret.Add(arr[mid + 1]);
                         }
                         else
                         {
                             ret.Add(Math.Abs(arr[mid]) > arr[mid + 1] ? arr[mid + 1] : arr[mid]);
                         }
                         break;
                     }
                     low = mid + 1;
                     binarySearch(low, high, arr, ref ret);
                     break;
                 }
             }
         }
 
         private static IEnumerable<int> GetABSMinValue3(IList<int> arr)
         {
             var ret = new List<int>();
             if (arr.Count < 2)
             {
                 ret.Add(arr[0]);
             }
             else
             {
                 if (arr[arr.Count - 1] <= 0)
                 {
                     ret.Add(arr[arr.Count - 1]);
                 }
                 else if (arr[0] >= 0)
                 {
                     ret.Add(arr[0]);
                 }
                 else
                 {
                     //方法三：二分法
                     binarySearch(0, arr.Count - 1, arr, ref ret);
                 }
             }
 
             return ret;
         }

　　测试用例：

View Code 
             var arr1 = new[] { -23, -22, -3, -2,-1, 1, 2, 3, 5, 20, 120 };
             var arr2 = new[] { -23, -22, -12, -6, -4 };
             var arr3 = new[] { 1, 22, 33, 55, 66, 333 };
             Console.WriteLine(string.Join(",", GetABSMinValue1(arr1)));
             Console.WriteLine(string.Join(",", GetABSMinValue1(arr2)));
             Console.WriteLine(string.Join(",", GetABSMinValue1(arr3)));
             Console.WriteLine(string.Join(",", GetABSMinValue2(arr1)));
             Console.WriteLine(string.Join(",", GetABSMinValue2(arr2)));
             Console.WriteLine(string.Join(",", GetABSMinValue2(arr3)));
             Console.WriteLine(string.Join(",", GetABSMinValue3(arr1)));
             Console.WriteLine(string.Join(",", GetABSMinValue3(arr2)));
             Console.WriteLine(string.Join(",", GetABSMinValue3(arr3)));
             Console.ReadKey();