Need help in implementing a binary search in C

Question

I am trying to write an iterative search in a C program.

The pseudo-code would look like this for it:

while length of list > 0

look at middle of list

if number found, return true

else if number is too high, only consider

left half of list

else if number is too low, only consider

right half of list

return false

I have already implemented a bubble sort (which I assume works). Here is my code right now. The search is currently linear. I need to somehow change it to a binary search (I would prefer to do it iteratively instead of recursively). I'm completely lost on how I should go about doing this though. Can someone please help me?:

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

#include "helpers.h"

/*
 * Returns true if value is in array of n values, else false.
 */

bool 
search(int value, int array[], int n)
{

// TODO: re-implement as binary search
int min = 0;
int max = n;
int i;

i=(min+max)/2;
    if(array[i] == value)
        {
        return true;
        }
    else if(min>=max)
        {
        return 1;
        }
    else if(array[i] > value)
        {
        max = i-1;
        }    
    else if(array[i] < value)
        {
        min = i+1;
        }
    return false;
}



/*
 * Sorts array of n values.
 */

void 
sort(int values[], int n)
{
//set smade to false to start
//declares the_end as n-1
bool smade = false;
int the_end = n-1;

// TODO: implement an O(n^2) sort
while(the_end > 0)
{
    for(int i = 0; i < the_end; i++)
    {
        int temp;
        if (values[i] > values[i+1])
        {
            temp = values[i];
            values[i] = values[i+1];
            values[i+1] = temp;
            smade=true;
        }
    

}
if(! smade)
    {
    break;
    }
the_end--;
}
return;
}

you're mixing up sorting and searching. you've been tasked with (binary) seach in an already sorted list. no need to sort it. — soulcheck
– soulcheck, Commented Dec 4, 2011 at 3:43
I understand. I was the one who made that sorting code, I now need to search that sorted list using a binary search. It took me a long time to even figure out how to do the bubble sort code. I have no idea how to approach this search. — user1079683
– user1079683, Commented Dec 4, 2011 at 3:45

David Schwartz · Accepted Answer · 2011-12-04 03:47:15Z

4

You just translate your pseudo-code into code. I'll give you some more refined pseudo-code:

1) Set minimum possible location for thing we're looking for (min) to zero.

2) Set maximum possible location for thing we're looking for (max) to the highest-possible location.

3) Compute a location loc as (min+max)/2.

4) Check if loc holds the object we're looking for. If so, stop, we found it.

5) Check if min>=max. If so, stop, it's not here.

5) If the object at loc is too high, set max to loc-1. (Because the maximum location at which it could be is one less than loc, since loc is too high.)

6) If the object at loc is too low, set min to loc+1. (Same logic, the other way around.)

7) Go to step 3.

answered Dec 4, 2011 at 3:47

David Schwartz

184k18 gold badges229 silver badges293 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

user1079683 Over a year ago

This was REALLY helpful. Is there any way I can show you what I wrote besides just editing my main post? I hopefully did what you wrote out, but I'm still learning so I could be completely off (hence why I want you feedback on what I did if you don't mind).

David Schwartz Over a year ago

You can update your question or you can post a link to a site like 'pastebin'.

user1079683 Over a year ago

I just updated the main one. It seems to run fine (the top part). The bottom part that I posted before this edit is full of errors though it seems (which has nothing to do with your thing, probably my mistakes). Anyhow, do you think I did what you said correctly? Also, do you have any idea why the sort part of this code is riddled with issues?

user1079683 Over a year ago

Edited it further to where it seems the sort (bottom) part works now. There seems to be a problem with the top part though (search part). It has something to do with me using 'i'. I'm guess assuming I did everything else correctly (still not sure), that I need to put something else inside the array[]. Just wanted to update (updated in main post as well).

David Schwartz Over a year ago

You have array[i] in a lot of places where you just want i.

|

havexz · Accepted Answer · 2011-12-04 05:18:17Z

1

Soln;

unsigned char  search(int value, int array[], int n)
{
  int start = 0;
  int end = n;
  int mid;

  // We ll exit the while loop if we just started overlapping 
  while(start<=end)
  {
    // Calculating the new mid point
    // Can also be written as mid = (start + end)/2;
    mid = start + (end-start)/2;
    if(value == array[mid])
      return 1;

    // If value is less we search on the left side
    if(value < array[mid])
      end = mid - 1;
    else
      start = mid + 1;
  }
  return 0;
}

answered Dec 4, 2011 at 5:18

havexz

9,6202 gold badges36 silver badges30 bronze badges

Comments

Hot Licks · Accepted Answer · 2011-12-04 03:47:41Z

0

You have the algorithm there. Just start with two index values -- low and high. Set them initially to the first and last entries in the array.

Next pick an (integer) value midway between high and low. Probe that array element. If it's equal to the desired value, you're done. If it's below/smaller/earlier than the desired value then set "low" to the probe element index +1. If it's above/larger/later than the desired value, set "high" to the probe element index -1. Then go back (in your while loop) and pick a new "midway" value.

If you get to where low > high (check in the while condition) then the value is not found.

(I'll add that the algorithm is basically simple, but can be frustratingly buggy if you don't think it out well and try to take some shortcuts.)

answered Dec 4, 2011 at 3:47

Hot Licks

47.8k19 gold badges96 silver badges156 bronze badges

2 Comments

user1079683 Over a year ago

I tried it out with the above posters help. It seems to still be wrong though. In case David can't respond, do you know why the above isn't working? I think it has to do something with putting i in things (and I shouldn't be). Also, possibly I am way off from what I should be doing.

Hot Licks Over a year ago

Critical step: Then go back (in your while loop)

Collectives™ on Stack Overflow

Need help in implementing a binary search in C

3 Answers 3

9 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

9 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related