1

I'm solving the following programming question: 

Given a sorted integer array and a number, find the start and end indexes of the number in the array. 

Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6} 
Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1} 

Complexity should be less than O(n)

My Solution is as follows: 

public static void  findStartEndIndex(int[] arr, int elem) {

      int elemIndex = binarySearch(arr, elem, 0, arr.length);

      if(elemIndex == -1)
         System.out.println("-1,-1");

      int lowIndex = elemIndex - 1;
      int highIndex = elemIndex + 1;

      //Find the first index in the lower half of the array

      while(lowIndex >= 0 && (elemIndex = binarySearch(arr, elem, 0, lowIndex)) != -1)
         lowIndex = elemIndex -1;

      //Find the last index in the upper half of the array
      while(highIndex < arr.length && (elemIndex = binarySearch(arr, elem, highIndex, arr.length - 1)) != -1)
         highIndex = elemIndex + 1;

      System.out.println((lowIndex + 1) + ", " + (highIndex -1));

   }

I'm having difficulty trying to find the time complexity of the above program. Following is my approach:

From my understanding, the worst case will be when all the elements are same: {3,3,3,3,3,3} Finding the first occurence will cost me: O(logn) //Binary Search

For each half of the array(upper and lower), I'm calling binarySearch at most O(logn) times. So, the total complexity will be O(logn ^2)

Is this the correct analysis? And, is O(logn^2) better than O(n)?

4

3 回答 3

2 
O(log2n) = O(log2+logn)
Now log2 is a constant. 
So O(log2n) = O(log2+logn) = O(1) + O(logn) = O(logn)

但是您的代码对给定整数的任何出现进行二进制搜索。<-log(n)
然后它找出最左边和最右边的出现。<-log(a)+log(b)第一次出现在a和a+b = n。

所以总复杂度是O(log(n)+log(a)+log(b)) = O(log(n*a*b)) = O(log(n))

编辑：等等！我误读了你的代码。在找到您找到的第一个匹配项后，可以在 O(logn) 时间内找到最左侧和最右侧。

基本上，您可以跳过查找任何事件的第一部分，并且可以在 O(logn) 中完成。你必须给出这样的条件： 

while A[i] != q or A[i-1] != A[i]:
    if A[i] < q: low = i + 1
    else: high: = i - 1

结束循环后，i将是q.

while A[i] != q or A[i+1] != A[i]:
    if A[i] > q: high = i - 1
    else: low = i + 1

结束循环后，i将是q.

Wherelow和high是从哪里到哪里查找查询以及i = low+high/2在每个步骤中的索引。

警告：您只需要处理一些其他情况，例如i永远不会消失[0..length of list-1]或列表中没有q。

这两部分都需要O(logn)时间，因此总时间复杂度O(logn)将比O((logn)^2)

于 2013-07-21T04:53:08.737 回答
1

关于复杂性：

如果您的意思是O((log(n))^2)：

定义m = log(n)，你得到：

O((log(n))^2) = O(m^2)

O(n) = O(e^log(n)) = O(e^m)

哪个显示O((log(n))^2)渐近优于O(n)。

如果您的意思是O(log(2n)：

O(log(2n) = O(log(2)+log(n)) = O(log(n))

所以也比O(n).

于 2013-07-21T04:03:24.867 回答
0

我是这样写程序的

int[] secondarr = new int[]{0,0,2,3,3,3,3,4,7,7,9};
    int searchNum = 3;
    int min = -1,max=-1;
    int noOfTimesLoopExecuted = 0;
    for(int ind=0, stop=0;ind<secondarr.length && stop==0;ind++) {
        if(searchNum>=secondarr[ind]){
            if(searchNum==secondarr[ind]){
            if(min==-1){
                min=ind;
            } else {
                max=ind;
            }
            }
        } else {
            stop = 1;
        }
        noOfTimesLoopExecuted = ind;
    }
    System.out.println("start index:"+min+","+"end index:"+max);
    System.out.println("noOfTimesLoopExecuted:"+noOfTimesLoopExecuted);
于 2015-05-28T07:50:58.483 回答