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

Question

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.");

to

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"));
}

Answer 1

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:

1. key is less than 1st element in array,
2. key is greater than last element in array, and
3. 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)