Binary Search of an Integer Array

Thanks a lot. This program was a real help.

There might be a problem:
If beg and end are both real address for a, which means they are multiple of 4, should the following calculation revised to mid=beg+=2n?
(The size of int is 4)

No there is no problem, sorry guys.

The compiler will handle that, for any data type, automatically.

It's a bit awkward because you're working with mid and other variables, as pointers, instead of as an index.

Also, you repeat the calculation and assignment line of code for mid, twice. Move it to the top of the while loop, and you can just do it one time.

It appears to be good workable code. For a snippet, I would have hoped for a sort better than bubble sort, however. Even though it's an optimized bubble sort, it's still a big step down.

It's ironic that we get way faster computers, only to have the slowest sorter, re-emerge in popularity.

use the following numbers and explain how a binary search works.we want to know if 7 are in this list of items.show all the steps
34 28 4 16 9 8 35 27 7

A binary search just takes a guess on the answer, and if the guess is too high, it cuts down the top of the search to one element's value below the guess. If the guess is too low, it brings up the bottom value of the search, to one element's value, above your guess.

So every time you guess and miss, you cut the search space into an ever smaller search space. Indeed, on each guess it makes, since it guesses the middle number (and unless that guess is correct), the search space is cut in half! ;)

In order to work, the values being searched, must be sorted. Since your numbers aren't sorted yet, that would be the necessary first step.

Instead of posting your assignment, post your assignment AND your attempt to solve it, AND what has you stumped, next time.

And Welcome to the Forum! ;)

Hello
I have an assignment regarding binary search
we have to search for an employee and his/her details from an array of structures
The above program really helps
But i am not getting why in "if(*mid!=target && beg<=end) "....beg<=end condition is required
I ran the program without it but nothing changed

Maybe you should read this Code Snippet then, as well as the posts.
Follow the code using pencil and paper to understand code in general.

Can someone please explain to me why we don't hit memory past the top end of the array under some circumstances with this algorithm?

In a very simple example with an array of 2 numbers, say 5 and 10, and we're looking for a target of 20, which we shouldn't find as it's too big.

First time through beg points at 5, mid points at 10 and end points off the end of the array which is fine, although I'm not sure why we want this? Why not set it to n - 1 so it's at least pointing to the last element in the array.

So, we do the compare and see that target > *mid so we execute beg = mid + 1; but this now means that beg is pointing off the end of the array. And then mid = beg += n/2 sets mid off the end of the array too! So now all three pointers point outside the array. Or am I missing something?

Would just setting beg = mid; fix the problem for a tiny loss of performance?

Any thoughts would be much appreciated.

Thanks.

Apologies, while problem still stands, I didn't think my suggested solution through - we have to move one of beg or end each time through the loop otherwise we can get into infinite loops. My suggestion fails with example I've just given if the target is 7.

Re-thinking, would setting n = n-1 at the top work? i.e. just before end = &a[n];

Hmm, on further inspection, the original algorithm also doesn't handle the case where n = 0.

Collecting a few ideas from a few other sites and doing a bit of testing, here's my preferred solution for anyone who's interested (it is slightly more explicit with less pointer shifting, but equally quick or quicker when compiled in the random tests I ran)...

int* pBase = &a[0];
    int nIdxLeft   = 0;
    int nIdxRight  = GetSize() - 1;
    int nIdxMiddle = 0;
    int nMiddleValue = *pBase;

    while (nIdxLeft <= nIdxRight)
    {
        nIdxMiddle = (nIdxLeft + nIdxRight) / 2;
        nMiddleValue = *(pBase + nIdxMiddle);
        if (nMiddleValue == dwTarget)
            break;
        else if (nMiddleValue > dwTarget)
            nIdxRight = nIdxMiddle - 1;
        else
            nIdxLeft = nIdxMiddle + 1;
    }

These "snippets" are not checked by anyone beyond a cursory look. They're typically coded by students, and shouldn't be taken as examples of great functions, in detail. Indeed, some have been dreadful, and I've shown it in detail.

In this case, you can tell it's less than elegant, simply because it repeats lines of code. It's less than efficient, because it repeats the comparison to target twice, in every loop.

It's alright if the pointers run off the boundary of the array, (or the index does), as long as the array is not referenced at that time (or the pointer isn't dereferenced). The idea it seems, is that the while loop test will fail, before that illegal comparison will be made.

I would not use any of these snippets, without thoroughly checking it out and testing them. This one is obviously, poor code. It does get the general idea across. That has some merit. I can't give it high marks otherwise, however.

// I think u can realize this method......
#include<stdio.h>
int sort(int arr[],int n) // Sorting the array..... here i use insertion sort but u can use any sorting method.....
{
	int i,j,temp;
	for(i=1;i<n;i++)
	{
		temp=arr[i];
		j=i-1;
		while(temp<arr[j] && j>=0)
		{
			arr[j+1]=arr[j];
			j=j-1;
		}
		arr[j+1]=temp;
	}
}
int get_data(int arr[],int n) // Gte data for array...
{
	int i;
	printf("Enter data for array :\n");
	for(i=0;i<n;i++)
	{
		scanf("%d",&arr[i]);
	}
	
}
int out_data(int arr[],int n) // Out data in the array....
{
	int i;
	printf("After sorting......\n\n");
	for(i=0;i<n;i++)
	{
		printf("%d ",arr[i]);
	}
}
int bi_search(int a[], int low, int high, int target) // Searching function......
{
    if (high < low)
        return -1;
    int middle = (low + high)/2; 
    if (target < a[middle])
        return bi_search(a, low, middle-1, target);
    else if (target > a[middle])
        return bi_search(a, middle+1, high, target);
    else if (target == a[middle])
        return middle;
}
main()
{
	int n=10,arr[20],k,b;
	get_data(arr,n);
	sort(arr,n);
	out_data(arr,n);
	printf("\n\nEnter value to search :");
	scanf("%d",&b);
	k=bi_search(arr,0,n-1,b);
	if(k==-1)
	printf("-->%d is not found......!\n",b);
	else
	printf("\n-->%d is found......!\n\n",b);
}

I'm always skeptical when I read code that has an index or pointer that runs out of the array bounds. The standard says you MAY be sure that it's OK, but only for 1 element AND you are never to work with the value at that address.

Code with no supporting tests, are another thing I'm cautious about. If you say that a program you post is good at something, I expect at least a little data from your testing, to support that conclusion.

There's a good deal of "hand waving and hot air" regarding programs, and I've read some great examples of it, by notable professors even. In the latest scam, the professor claimed a VERY fast prime number generator -and it was BLAZING fast. Only later did you learn it was so fast, partly because it HAD A LIST OF PRIME NUMBERS, EMBEDDED IN THE CODE! Oh for crying out loud!!

Another common example is someone claiming that their new sorting algorithm is "Faster than Quicksort". Sure, because Quicksort is an old algorithm, and the early versions weren't well studied yet. So you can easily beat the Quicksort versions from 20 years ago, but that's *NOT* beating a modern version of Quicksort!

Well, they get their names in the scholarly publications, and their tenure is quite secure, etc. Still, it's misleading at best.

I don't know anything about this binary search version. When I was a kid, we used to play a "Guess the number I'm thinking of" game, from time to time. My version of the Binary search reflects the way us kids learned to play the game, and it's plenty fast enough, even for a speed fanatic like me. When I see a version that is at least 5% faster, and has data to support it, I'll look into it.

Until then, I'm just reading an interesting post.

A description of Binary Search and the algorithm can be found here:
http://codinghavok.wordpress.com/2011/12/31/basics-i-searching/