0

I have written a binary search like following. When I try to find 10, it's not showing me the result. What am I missing??

// BinarySearch.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"
#include <iostream>
using namespace std;

void BinarySearch(int arr[],int value);
int * insertionshot(int arr[]);
int _tmain(int argc, _TCHAR* argv[])
{
int arr[10] = {1,2,3,10,5,9,6,8,7,4};
int value;
cin >> value ;
static int *ptr;// = new int[10];
ptr = insertionshot(arr);
BinarySearch(ptr,value);
return 0;
}

int * insertionshot(int arr[])
{
int ar[10];
for(int i =0;i < 10; i++)
{
    ar[i] = arr[i];
}

int arrlength = sizeof(ar)/sizeof(ar[0]);
for(int a = 1; a <= arrlength -1 ;a++)
{
    int b = a;
    while(b > 0 && ar[b] < ar[b-1])
    {
        int temp;
        temp = ar[b-1];
        ar[b-1] = ar[b];
        ar[b] = temp;
        b--;
    }
}
return ar;
}

void BinarySearch( int a[],int value)
{
int min,max,middle;
min = 0;
int ar[10];
for(int i =0;i < 10; i++)
{
    ar[i] = a[i];
}
//printf("size of array = %d",sizeof(arr));
max = (sizeof(ar)/sizeof(ar[0]) -1);
middle = (min+max)/2;

while(min <= max)
{
    if(ar[middle] == value)
    {
      cout << "The value found" << ar[middle];
      break;
    }
    else if(ar[middle] < value)
    {
        min = middle +1;
    }
    else if(ar[middle] > value)
    {
        max = middle-1;
    }
    middle = (min+max)/2;
}
}

Finally i made it work,I think this code does not have any problem.This could help any one

 // BinarySearch.cpp : Defines the entry point for the console application.
 //

#include "stdafx.h"
#include <iostream>
using namespace std;

void BinarySearch(int arr[],int value);
int * insertionshot(int arr[],int);
int _tmain(int argc, _TCHAR* argv[])
{
int arr[10] = {1,2,3,10,5,9,6,8,7,4};
int * arr1 = new int[10];
for(int i = 0;i< sizeof(arr)/sizeof(arr[0]);i++)
{
    arr1[i] = arr[i];

}

int value;
cin >> value ;
int *ptr = new int[10];
ptr = insertionshot(arr1,10); // address of sorted array will be returned.
BinarySearch(ptr,value);
arr1 = 0;
ptr =0;
delete arr1;
delete ptr;
return 0;
}

int * insertionshot(int arr1[],int n)
{

for(int a = 1; a <= n -1 ;a++)
{
    int b = a;
    while(b > 0 && arr1[b] < arr1[b-1])
    {
        int temp;
        temp = arr1[b-1];
        arr1[b-1] = arr1[b];
        arr1[b] = temp;
        b--;
    }
}
return arr1;
}

void BinarySearch( int a[],int value)
{
int min,max,middle;
min = 0;
int ar[10];
for(int i =0;i < 10; i++)
{
    ar[i] = a[i];
}
max = (sizeof(ar)/sizeof(ar[0]) -1);
middle = (min+max)/2;

while(min <= max)
{
    if(ar[middle] == value)
    {
      cout << "The value found" << ar[middle];
      break;
    }
    else if(ar[middle] < value)
    {
        min = middle +1;
    }
    else if(ar[middle] > value)
    {
        max = middle-1;
    }
    middle = (min+max)/2;
}
}
4
  • Hi. Asking people to spot errors in your code is not especially productive. You should use the debugger (or add print statements) to isolate the problem, by tracing the progress of your program, and comparing it to what you expect to happen. As soon as the two diverge, then you've found your problem. (And then if necessary, you should construct a minimal test-case.) Commented Apr 5, 2014 at 18:16
  • 4
    First : binary search requires sorted array ! Commented Apr 5, 2014 at 18:16
  • Others have explained why your progam gives an answer you don't expect, but there are other problems with it: 1. The binary search should be separated out into its own procedure, and 2. There are ways to write the program that find either the first or the last occurrence of the value you're searching for, and that are also likely (but not certain) to be faster. Commented Apr 5, 2014 at 18:25
  • Please, don't use TCHAR and its ilk unless you are porting ancient Windows programs. Commented Apr 5, 2014 at 18:38

2 Answers 2

6

You're missing the most important part of a binary search: The collection you search in must be sorted.

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

8 Comments

I checked in Wiki but did not find how can I sort this.Could you please give a example code.Thanks.
@bapi You initialize the array manually, with very few items. It's not hard to make it sorted.
@bapi, since you are a novice programmer, I am rather curious why you are using C++, a peculiarly hairy and unpleasant programming language.
Hello Joachim Pileborg , as per your suggestion I have used insertion shot,still having problem? Could you please suggest.Thanks.
@bapi Now you have another and even worse problem: Undefined behavior. In the sorting function (as I guess it is) you return a pointer to the local array ar. An array that goes out of scope once the function returns. What will the returned pointer now point to? You have the array hard-coded in the source, why not simply rearrange that so it's sorted?
|
0

For binary search, the array should be arranged in ascending or descending order.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.