알 수없는 크기의 배열에 대한 이진 검색

Question

배열이 있고 해당 배열에서 요소를 찾고 싶다고 가정하면 이진 검색을 사용하여 해당 배열의 요소를 검색하고 해당 배열이 이미 정렬되어 있고 배열의 크기를 알 수없는 이유는 무엇입니까? . 선형 검색을 적용 할 수 있지만 선형 알고리즘보다 빠른 검색을 위해 노력하고 있습니다. 당신이 배열 범위를 벗어 떨어진 여부를 테스트 할 수있는 경우

Answer 1

는, 당신은 수정 된 이진 검색을 사용할 수 있습니다 (1 기반의 배열을 가정) :

1. 낮은 = 1 위 = 1;
2. (A [upper] < 요소) upper * = 2;
3. 정상적인 이진 검색은 (lower, upper).

그렇지 않으면 실제로 할 수있는 방법이 없습니다. 필요한 요소와 동일한 어딘가를 찾았 으면 이미 배열에서 벗어 났는지 알 수 없습니다.

내가 (자바 esqe 언어에서) 이런 식으로 뭔가를 시도 할 수 있습니다 :

Answer 2

여기 시작합니다. 배열은 "C와 같은"이고 마지막에 0이있는 경우, 당신은 또한 확인해야 할 것 :

int endOfArray = 10; 
try { 
    while (true) { 
    int value = theArray[endOfArray*2]; 
    if (value > requestedValue) // good enough 
     return doBinarySearch(theArray, 0, endOfArray, requestedValue); 
    else 
     endOfArray*=2; 
    } 
} 

catch (ArrayIndexOutOfBoundsException aioob) { 
    // we know that the end of the array is less than endOfArray*2 but > endOfArray 
    // do something clever here TBD. :-) 
} 

참고 나중에 추가 (정수 배열을 가정). BTW, 누군가 "여기 영리한 것"부분에 대한 간단한 해결 방법이 있다면 답을 자유롭게 편집하십시오.

Answer 3

다음은 (테스트하지 않았습니다) 작동해야하지만 이진 검색과 같은 경계를해야한다, O(log(n)) : 여기

private bool hasValue(int[] array, int search, int start, int end) 
{ 
    int mid = (start+end)/2; 

    try 
    { 
     //Check to see if we can grab the value 
     int value = array[mid]; 

     //If we are here, we are in the array 

     //Perform the binary search 
     if (value==search) 
      return true; 
     else if (end <= start) 
      return false; 
     else if (value>search) 
      return hasValue(array, search, start, mid); 
     else 
      return hasValue(array, search, mid, end*2); 

    } 
    catch(ArrayIndexOutOfBoundsException e) 
    { 
     //If we are here, then we were outside the array, so 
     //loop through the lower half 
     return hasValue(array, search, start, mid); 
    } 


} 

public bool hasValue(int[] array, int search) 
{ 
    // 0 is the start of the array (known) 
    // 1 is the end--start with any number that is greater than max(start, 1) 
    return hasValue(array, search, 0, 1); 
} 

는 배열 A는 가정 예를 들어 사용

// 2 is the value you are looking for 
bool hasTwo = hasValue(array, 2); 

Answer 4

입니다 정렬 된 (그렇지 않으면 이진 검색을 수행 할 수 없습니다.) 검색중인 요소가 k라면 k < A [i]와 같은 인덱스 i를 찾은 다음 1에서 i (1- 인덱스 배열). 왜냐하면 일단 k < A [i], k는 정렬 된 요소 A [1..i]의 범위에서 발견되거나 (또는 ​​발견되지 않음) 보장되기 때문입니다.

색인 i를 찾으려면 i = 1에서 시작하고 k> A [i]이면 두 배로 만듭니다. 이것은 검색 범위를 두 배로하는 것을 제외하고는 바이너리 검색과 같아서 O (log n) 실행 시간을 갖습니다.

알고리즘은 같은 것이있다 : 집합 I = 1 다음 K까지 반복 < = A [I] :

• 경우 K> A [I]는 그때 = 1 2

을 *하자

k == A [i]이면 완료됩니다. 그렇지 않으면 A [1..i]에서 평소와 같이 2 진 검색을 수행하십시오.

Answer 5

이것은 나를 위해 일하고 있습니다. 이것은 O (log N + log N), 즉 여전히 O (log N)입니까? 이 방법은 효율적인 방법으로 하위 배열에도 적합합니다. O (로그 N)

static int bSearch (int needle, int[] arr) 
    { 
    boolean done = false; 
    int i = 1; 
    int lower = 0; 
    int upper = 1; 
    int temp; 
    while (!done) 
    { 
     try{ 
      if (needle == arr[upper]) 
       return upper; 
      else if (needle > arr[upper]) 
      { 
       temp = lower; 
       lower = upper; 
       upper = temp + (int) Math.pow(2,i); 
       i = i + 1; 
      } 
      else 
      { 
       done = true; 
       break; //found the upper bounds 
      } 
     } 
     catch (IndexOutOfBoundsException e) 
     { 
     upper = (upper -lower)/2; 
      i = 0; 
     } 
    } 
    if (done == true) 
     //do normal binary search with bounds lower and upper and length upper-lower 
    else 
     return -1; 
    }