Path: csiph.com!fu-berlin.de!uni-berlin.de!news.dfncis.de!not-for-mail
From: Frank Tetzel <s1445051@mail.zih.tu-dresden.de>
Newsgroups: comp.lang.c
Subject: Re: Simple program to implement binary search
Date: Thu, 12 Nov 2015 17:45:30 +0100
Lines: 74
Message-ID: <20151112174530.49d8a2ea@archthink>
References: <af16475b-9f9c-46f8-98c5-9353f82423da@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
X-Trace: news.dfncis.de ZOsed6sP6KFx+YXXo6Pn2AYffIlQ/oLy5Rbhfq/EdJi50k
X-Newsreader: Claws Mail 3.13.0 (GTK+ 2.24.28; x86_64-unknown-linux-gnu)
Xref: csiph.com comp.lang.c:75838

> // Program to perform binary search
> 
> #include <stdio.h>
> #include <stdbool.h>
> 
> bool binary_search(int search_value, int numbers[], int min_val, int
> max_val);
> 
> bool search(int value, int values[], int n);
> 
> int main(void)
> {
>     int array[] = {1, 2, 3, 4, 5};
>     int number;
>     
>     printf("Name your number: \n");
>     scanf("%i", &number);
>     
>     if (search(number, array, 5))
>     {
>         printf("\nFound your number!\n\n");
>         return 0;
>     }
>     else
>     {
>         printf("\nDidn't find your number.\n\n");
>         return 1;
>     }
> }
> 
> // Function to perform binary search 
> bool binary_search(int search_value, int numbers[], int min_val, int
> max_val) {
>     
>     if (max_val < min_val)
>         return false;
>     
>     int mid_index = (max_val + min_val) / 2;
>     
>     if (search_value > numbers[mid_index])
>         binary_search(search_value, numbers, mid_index+1, max_val);
>     else if (search_value < numbers[mid_index])
>         binary_search(search_value, numbers, min_val, mid_index-1); 
>     else
>         return true;
>     
>     return false;
> /** I had to add the last return false; part because 
> without it the compiler generated a warning:
> warning: control reaches end of non-void function **/

Think about it. The compiler has a reason to say that. Try to follow
all possible paths in this function. Which of them does not have a
return statement? And is this correct? This return false at the end is
wrong.

Keep in mind that this is a recursive function. Think about the
recursion stack and what one return statement does.

> }
> 
> // Function that searches for required value using binary_search
> function bool search(int value, int values[], int n)
> {
>     int min = 0;
>     int max = n-1;
>     
>     if (binary_search(value, values, min, max))
>         return true;
>     
>     else
>         return false;
> }