阿里笔试题(二分查找)

布满荆棘的人生 2022-10-22 12:58 157阅读 0赞

给定一个排好升序的数组A\[1\]、A\[2\]、……、A\[n\]，其元素的值都两两不相等。请设计一高效的算法找出中间全部A\[i\] = i的下标。并分析其复杂度。（不分析复杂度不得分） （阿里巴巴2013技术类笔试题）

分析：  
首先肯定不能选择遍历了，遍历的时间复杂度为O(n)，那这里更高效一点的，算法设计的时间复杂度理应为O(logn)，具体如何设计？

其实很容易想到的是二分法去处理这个问题，根据题目的条件：元素值两两不等，对于A\[i\] = i的这些下标肯定是连续的，不会出现在断序的情况。

传统的二分法一般针对某个元素进行搜索，在这里其实可以搜索多个相对的元素，首先我们假想这样一个数组A\[i\]-i这个数组，这是会发现这个数组分为3个部分，前面的值小于0，中间的部分等于0，后面的部分大于0，而我们要寻找的是中间等于0的部分，而根据上面的分析，中间等于0的部分是连续的，因此我们寻找中间部分的最左端，如果当前位置是mid，那么仅仅要推断当前A\[mid\] - mid是否小于零、后一个元素A\[mid+1\] - (mid+1) == 0即可了，满足这两个条件，就找到了中间部分最左端的位置。

下面是代码：

#include <iostream>
    #include<stdio.h>
    using namespace  std;
    int BinarySearch( int a[],  int len)
    { 
        int left = 0;
        int right = len;
        int mid;
        while (left <= right)
        { 
           mid = (left + right)/2;
           if (mid == 0 && a[mid] == mid)  // 数组只有一个元素且符合条件
              return 0;
    
           if (a[mid]-mid < 0 && a[mid+1]-(mid+1) == 0) // 左边界是前一个<0，且后一个=0
              return mid+1;
    
           if (a[mid] - mid >= 0)  // 二分查找边界：若差值大于0，则右边界为中间位置减1
              right = mid-1;
           else
              left = mid+1;
        }
        return -1;
    }
    int  main()
    { 
        //int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        int a[] = { -7, -1, -4, -2, 4, 5, 6, 8};
        //int a[] = {-5, -4, -3, 5, 6, 7};
        int len =  sizeof (a)/ sizeof ( int );
        int idx = BinarySearch(a, len);
    
        if (idx != -1)
        { 
           while (idx < len)
           { 
              if(a[idx] == idx)
              { 
                  printf ( "%d " , idx);
                  idx++;
              }
           }
        }
        else
        { 
           printf ( "Not found\n" );
        }
        getchar();
    
    
        return 0;
    }