本文主要是介绍[经典面试题]排序数组中绝对值最小元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目】
| 题目为：
有一个已经排序的数组（升序），数组中可能有正数、负数或0，求数组中元素的绝对值最小的数，要求，不能用顺序比较的方法（复杂度需要小于O（n）），可以使用任何语言实现 例如，数组{-20，-13，-4, 6, 77,200} ，绝对值最小的是-4。 |
【分析】
给定数组是已经排好序的，且是升序，没有重复元素。
一个简单的思路，就是一次性遍历数组，求出数组的元素的绝对值的最小值，这样的时间复杂度为O(n)。
但是，这样就浪费了题目的一个条件：数组是已经排好序的。所以，需要对原来的题目进行转换。考虑到数组有序，利用二分查找原理。
求数组中绝对值最小的元素，与0离得最近绝对值越小。基于这个原理设计代码。
分三种情况：
（1）如果全是正数，返回第一个元素值。if(A[0] >= 0)
（2）如果全是负数，返回最后一个元素值。if(A[n-1] <= 0)
（3）有正有负，利用二分查找找到0的插入位置，如果正好找到0的位置，0就是绝对值最小的元素，
如果没有找到0，插入位置的左右元素比较绝对值大小 ，返回较小者OK。
【代码】
/*********************************
* 日期：2015-01-29
* 作者：SJF0115
* 题目: 排序数组中绝对值最小元素
* 来源：百度
* 博客：
**********************************/
#include <iostream>
#include <algorithm>
using namespace std;int MinAbs(int A[],int n){if(n == 1){return A[0];}//if// 只有正数if(A[0] >= 0){return A[0];}// 只有负数if(A[n-1] <= 0){return A[n-1];}// 找到0的插入位置int target = 0;int left = 0,right = n - 1;int mid;while(left <= right){mid = left + (right - left) / 2;// 中间元素等于目标if(A[mid] == target){return A[mid];}// 目标在左半部分else if(A[mid] > target){right = mid - 1;}// 目标在右半部分else{left = mid + 1;}}//while// 绝对值最小if(abs(A[left]) < abs(A[right])){return A[left];}return A[right];
}int main(){//int A[] = {-6,-5,-4,-3,-2,-1};//int A[] = {-6,-5,-4,1,2,3};//int A[] = {1,2,3,4,5,6};int A[] = {-20,-13,-4,6,77,200};int n = 6;cout<<MinAbs(A,n)<<endl;;return 0;
}
这篇关于[经典面试题]排序数组中绝对值最小元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
