面试题81：有序数组中绝对值最小的元素

本文主要是介绍面试题81：有序数组中绝对值最小的元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

给定一个有序整数序列（非递减序），可能包含负数，找出其中绝对值最小的元素，比如给定序列-5、-3、-1、2、8则返回1。

思路：

由于是有序数组，而且是搜索问题，所以首先考虑二分查找法。

对于每个子数组，可以考虑一下几种情况：

1）如果给定的序列中所有的数都是正数，那么数组的第一个元素就是结果。

2）如果给定的序列中所有的数都是负数，那么数组的最后一个元素就是结果。

3）如果给定的序列中既有正数，又有负数，那么绝对值的最小值一定出现在正数和负数的分界处。

#include <iostream>
#include <algorithm>
using namespace std;const int N = 100;
const int poolN = 3;bool SameSign(int m, int n)
{if ((m >> 31) == (n >> 31)) return true;return false;
}int MiniNumAbsoluteValue(int *arr, int n)
{int low = 0;int high = n - 1;if (SameSign(arr[low], arr[high]))return arr[low] >= 0 ? arr[low] : arr[high];while (low < high){if (low + 1 == high) return (abs(arr[low] < abs(arr[high])) ? arr[low] : arr[high]);int mid = (low + high) >> 1;if (SameSign(arr[low], arr[mid]))//不用担心low到high全为正的情况，如果这样，则所有的都为正了{low = mid;continue;}if (SameSign(arr[mid], arr[high])){high = mid;continue;}}return arr[low];
}int main()
{int arr[] = { -5, -3, -1, 2, 8,9 };cout << MiniNumAbsoluteValue(arr, 6) << endl;return 0;
}

这篇关于面试题81：有序数组中绝对值最小的元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---