DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Binary Search Demo Program

12.11.2010
| 2557 views |
  • submit to reddit
        

//
// binary_search.cpp
//
// Demo program of binary search.


#include <stdio.h>						// uses printf 
#include <stdlib.h>

int binary_search(int data[],int search_item,int length)
{
  int min =-1;
  int max = length;
  while(true)
  {
    // found condition.
    if(data[(min+max)/2]==search_item)
      return (min+max)/2;
    // termination condition.
    if(min==max)
    {
      return -1;
    }
    // else
    if(data[(min+max)/2]<search_item)
    {
      min=(min+max)/2;
    }   
    else{
      max=(min+max)/2;
    }

  }
}


int main()
{
#define MAX_ARRAY_SIZE 100
  // an array to binary_search.
  int int_array[MAX_ARRAY_SIZE];

  // fill this array from the stdin.
  int count=0;
  printf("please enter the numbers you want to sort -1 to end:\n");
  while(true)
  {
    int input;
    scanf("%i",&input);
    
    if(input==-1)
      break;
    else
      int_array[count]=input;  
    if(count>=MAX_ARRAY_SIZE)
      exit(0);
    count++;
  }
  

  // get the value that you need to search.
  int search;
  printf("Plese enter the value that you need to Search");
  scanf("%i",&search);
 
  // search.
  int result;
  if((result=binary_search(int_array,search,count))==-1)
  {
    printf("the value %i does not found in the array\n",search);
  }else{
    printf("the value %i is located at index %i\n",search,result);
  } 

  return 0;
}
    

Comments

Snippets Manager replied on Tue, 2007/06/05 - 11:43am

This algorithm is WRONG. Try searching the array {2} for the value 1. (so length = 1) First iteration: min = -1, max = 1, mid = 0 Second iteration: min = -1, max = 0, mid = 0 Third iteration: min = -1, max = 0, mid = 0 You're stuck in an infinite loop!