Recherche binaire - Contrôle égalité différée

Question

http://ideone.com/RT84T6

while (first <= last) { 
    // Assert: Array is sorted and first <= last 
    //Initialization:target is within (extremes inclusive) the range of first  and last. IE First<=x<=Last 
    mid = (first+last)/2; 
    //Maintenance: Increasing first to mid+1 if x>mid or decrease last to  min-1 if x<mid. 
    if (target < arr[mid]) last = mid-1; 
     else first = mid+1; 
    } 
    //Termination: target is not within the array. 
    return -1; 
if ((first <= target) && (arr[first]==target)) return 1; 
    else return -1; 
} 

Je reçois une sortie de -1 à chaque fois que je lance ma recherche binaire (détection différée de la version d'égalité).

Je n'arrive pas à déterminer où il en résulte un -1.

Answer 1

est ici une solution complète, y compris un pilote de test simple:

#include <stdio.h> 

// 
// Returns the array index if target is present. 
// Returns -1 if target is absent. 
// 
int bin_search(int *arr, int len, int target) 
{ 
    int first = 0; 
    int last = len - 1; 
    int mid; 

    while (first < last) { 
     mid = (first + last)/2; 
     // Note: We require mid < last for this to work. This should be 
     // the case since integer division uses "truncation towards zero". 

     if (arr[mid] < target) { 
      first = mid + 1; 
     } 
     else { 
      last = mid; 
     } 
    } 

    if (first == last && arr[first] == target) { 
     return first; 
    } 

    return -1; 
} 

int main() 
{ 
    static int a[5] = {1, 2, 3, 4, 5}; 
    int ix; 
    int i; 

    for (i = 0; i <= 6; i++) { 
     ix = bin_search(a, 5, i); 
     printf("%d: %d\n", i, ix); 
    } 

    return 0; 
} 

La sortie est:

0: -1 
1: 0 
2: 1 
3: 2 
4: 3 
5: 4 
6: -1 

Notez que j'ai inversé le test en boucle afin que last est mis à jour plutôt que first dans le cas où target a été trouvé. Cela garantit que last diminue dans ce cas. L'original pourrait également être mis au travail, mais nécessiterait la division par deux lors de la mise à mi-ronde plutôt que vers le bas.

J'ai également changé bin_search pour retourner l'index de la cible si elle est présente, et -1 si elle est absente.