Binary Search using a pointer in C

B

If you are a computer science student or wants to start learning Data structure using practical hands-on then you are landing in the right place. This practice is part of the Data structure subject taught in GTU (Gujarat Technological University) Diploma course, but it is not limited to this. You can use this tutorial to have a better understanding of detail explanations. if you like to get more out of this practice then I highly recommend you to do code follow along is a best possible way. To know more about Author please visit here

If you are curious about to know why searching is so important in problem-solving or in computer science? please check here well-written article given on Wikipedia.

There are many different searching techniques as follow:

  1. Linear Search.
  2. Binary Search.
  3. Jump Search.
  4. Interpolation Search.
  5. Exponential Search.
  6. Sublist Search (Search a linked list in another list)
  7. Fibonacci Search.
  8. The Ubiquitous Binary Search.

Let’s see Binary Seach technique in detail, shall we?
here is an algorithm you might find helpful before jump into the code itself.

Algorithm

// Perform binary search
function binary_search(A, n, T):
    L := 0
    R := n − 1
    while L <= R:  
       m := floor((L + R) / 2)  
       if A[m] < T: 
          L := m + 1  
       else if A[m] > T:
            R := m - 1
       else:
            return m
    return unsuccessful
/*
* @Author: abdulkaiyum
* @Date:   2019-07-22 08:35:51
* @Last Modified by:   abdulkaiyum
* @Last Modified time: 2019-07-22 09:19:20
*/

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

int Bsearch(int *array,int inputLength,int key)
{
	// Binary search works on sorted array, so let's make input list sorted first (ascending)
	int i,j,*temp;
	int low = 0,
		high = inputLength - 1,
		mid;

	int isFound = 0;

	temp = (int *) malloc(sizeof(int *));

	for (i = 0; i < inputLength - 1; ++i)
	{
		for(j = i+1; j < inputLength; ++j)
		{
			if((array + i) > (array + j))
			{
				*temp        = *(array + i);
				*(array + i) = *(array + j);
				*(array + j) = *temp;
			}  
		}
	}

	// Perform binary search
	// function binary_search(A, n, T):
 //    L := 0
 //    R := n − 1
 //    while L <= R:
 //        m := floor((L + R) / 2)
 //        if A[m] < T:
 //            L := m + 1
 //        else if A[m] > T:
 //            R := m - 1
 //        else:
 //            return m
 //    return unsuccessful

	while(low <= high)
	{
		mid = floor((low + high)/2);

		if(*(array+mid) < key)
		{
			low = mid + 1;
		}
		else if ( *(array + mid) > key)
		{
			high = mid - 1;
		}
		else
		{
			isFound = 1;
			break;
		}
	}
	return isFound;
}

int main(int argc, char const *argv[])
{
	
	int *inputArray,i;
	int count,key;

	printf("%s\n", "Please Enter number of Elements");
	scanf("%d",&count);

	inputArray = (int *) malloc(count * sizeof(int *));

	printf("%s\n", "Enter your numbers followed by enter key");

	for (i = 0; i < count; ++i)
	{
		scanf("%d",inputArray);
		inputArray++;
	}
	inputArray = inputArray - count;

	printf("%s\n", "Enter element you want to search in the array");
	scanf("%d",&key);

	if(Bsearch(inputArray,count,key) == 1)
	{
		printf("%s\n", "element found");
	}
	else
	{
		printf("%s\n", "element not found");
	}


	return 0;
}

1 comment

Recent Posts

Recent Comments

Archives

Categories

Email Subscriber