[经典面试题]排序数组中绝对值最小元素

【题目】

题目为：

有一个已经排序的数组（升序），数组中可能有正数、负数或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;
}