When number is not found in array it does not give me the desired output-CodePudding

Below code finds the desired key in array and prints it but when key is not found, I expect the search return -1 and print "Key not found." But this is not printed. Is there a mistake?

#include<stdio.h>

int binarySearch(int* arr, int size, int key){

    int low=0;
    int high=size-1;
    int mid=(low high)/2;      

    while(arr[mid]!=key){
    
        if(key>arr[mid]){
            low=mid 1;
            mid=(low high)/2;
        }
        if(key<arr[mid]){
            low=0;
            high=mid-1;
            mid=(low high)/2;       
        }   
        if(key==arr[mid]){
            return mid;
        }           
    }   
}

int main(){

    int intArr[10]={4,5,12,44,232,326,654,776,987,999};

    int res=binarySearch(intArr, 10, 1);

    if(res){
        printf("Key found at index: %d.", res);
    }else ("Key not found.");
}

Note: I made a mistake on syntax of this part. I corrected.

this

else ("Key not found.");

else (printf("Key not found.\n"));

It is working as intended after this correction. I also added @weatherwane' s suggestion and @poepew's suggestions.

Here is the working code:

#include<stdio.h>

int binarySearch(int* arr, int size, int key){
    
    int low=0;
    int high=size-1;
    int mid=(low high)/2;
    
    while(high-low>0){
        
        if(key>arr[mid]){
            low=mid 1;
            mid=(low high)/2;
        }
        if(key<arr[mid]){
            low=0;
            high=mid-1;
            mid=(low high)/2;       
        }   
        if(key==arr[mid]){
            return mid;
        }           
    }   
    return -1;
}

int main(){
    
    int intArr[10]={4,5,12,44,232,326,654,776,987,999};
    
    int res=binarySearch(intArr, 10, 43);
    
    if(res>=0){
        printf("Key found at index: %d.\n", res);
    }
    else (printf("Key not found.\n"));
}

CodePudding user response：

This problem occurs because you do not have a return statement for the so called 'not found' case. After your while statement add a return -1 case.


#include<stdio.h>

int binarySearch(int* arr, int size, int key){

    int low=0;
    int high=size-1;
    int mid=(low high)/2;  
    int i = 0;

    while(arr[mid]!=key ){
        i = mid;
        if(key>arr[mid]){
            low=mid 1;
            mid=(low high)/2;
        }
        if(key<arr[mid]){
            low=0;
            high=mid-1;
            mid=(low high)/2;       
        }   
        if(key==arr[mid]){
            return mid;
        }    
        if(i == mid){
            return -1;
        }
    }   
    return -1;
}

int main(){

    int intArr[10]={4,5,12,44,232,326,654,776,987,999};

    int res=binarySearch(intArr, 10, 99);
    typeof(res);
    if(res){
        printf("Key found at index: %d.", res);
    }
    else {
        printf("Key not found");
        
    }
}

EDIT: Also there was an infinite loop caused by the while loop, in order for the while loop presented in the question arr[mid] should not be equal to the key. which if the array does not contain the wanted element results in infinite loop. The solution I have added is to check if the new mid value is added or not. it is set to the initial value at the start of the loop and if it is not muted, it returns -1.

CodePudding user response：

Your implementation of an iterative bsearch using the test while (arr[mid] != key), is a bit awkward compared to the normal loop condition of while (low <= high), but you can write it this way.

You have three exit conditions to protect against:

key is less than 1st element in array,
key is greater than last element in array, and
key is within the range of 1st - last, but not present in the array.

The primary error in your logic is you only adjust low if key > arr[mid], and you only adjust high if key < arr[mid]. You never adjust both in response to a condition.

Putting it altogether, you would edit your approach and do:

int binarySearch (int *arr, int size, int key) {

  int low = 0,
      high = size - 1,
      mid;

  while (arr[mid] != key) {       /* loop while key not found */
  
    if (low > high) {             /* all possible values searched */
      return -1;                  /* return key not found */
    }
    
    mid = (low   high) / 2;       /* compute mid once per-iteration */
    
    if (key > arr[mid]) {
      low = mid   1;              /* only adjust low if key > element */
    }
    else if (key < arr[mid]) {
      high = mid - 1;             /* only adjust high if key < element */
    }
  }
  
  return mid;                     /* return index to key */
}

The traditional implementation of a bsearch controlling the loop with low <= high is written as follows:

int binarySearch (int *arr, int size, int key)
{
  int low = 0,
      high = size - 1,
      mid;

  while (low <= high) {
      
      mid = low   ((high - low) / 2);
      
      if (arr[mid] == key) {
          return mid;
      }
      else if (key < arr[mid]) {
          high = mid - 1;
      }
      else {
          low = mid   1;
      }
  }

  return -1;
}

You would need to dump to assembly to determine which provided the most efficient implementation. They will be within a few instructions of each other.

Let me know if you have questions.

(note: while the compiler may not care if there are no spaces in your code, your aging professor will -- always space your code adequately for readability)