Binary Search - Revision history

Proj user16 at 22:57, 8 December 2016

2016-12-08T22:57:28Z

Proj user16 at 08:24, 7 December 2016

2016-12-07T08:24:42Z

Proj user16: /* Binary Search */

2016-12-03T00:18:13Z

‎Binary Search

Proj user16: /* Binary Search */

2016-12-03T00:13:33Z

‎Binary Search

Proj user16: /* Binary Search */

2016-12-02T23:44:01Z

‎Binary Search

Proj user16: /* Binary Search */

2016-12-02T23:43:30Z

‎Binary Search

Proj user16 at 23:42, 2 December 2016

2016-12-02T23:42:17Z

Proj user16: /* Binary Search */

2016-12-02T23:41:46Z

‎Binary Search

Proj user16: /* Binary Search */

2016-12-02T23:40:53Z

‎Binary Search

Proj user16: /* Binary Search */

2016-12-02T23:40:15Z

‎Binary Search

@@ Line 49: / Line 49: @@
     scanf("%d",&n);													// defining the array size
-    int array[n];
+    int* array = (int*)malloc(n*sizeof(int));                        //allocating size of the array dynamically
     printf("Enter %d integers\n", n);
     for (int i = 0; i < n; i++)

@@ Line 14: / Line 14: @@
 '''Code Snippet'''
-<pre>
+<syntaxhighlight lang="c">
 #include <stdio.h>
@@ Line 23: / Line 23: @@
 	int first = 0, last = size - 1, middle = (first+last)/2;
-    while (first <= last) 						//looping over the array to find the matching element till all elements in each half are compared
+    while (first <= last) 											//looping over the array to find the matching element till all elements in each half are compared
+    {
-       if (array[middle] < key)						//if element is lesser than the key value
+       if (array[middle] < key)										//if element is lesser than the key value
      	  first = middle + 1;
-       else if (array[middle] == key) {					// if matched with key
+       else if (array[middle] == key) {								// if matched with key
      	  return middle+1;
           break;
@@ Line 33: / Line 33: @@
        else
+       {
-     	  last = middle - 1;						// reducing the size of the halves
+     	  last = middle - 1;										// reducing the size of the halves
+       }
-       	 middle = (first + last)/2;					//re-calculating the middle value after each iteration
+       	 middle = (first + last)/2;									//re-calculating the middle value after each iteration
+    	   }
     return 0;
@@ Line 47: / Line 47: @@
     printf("Enter number of elements\n");
-    scanf("%d",&n);							// defining the array size
+    scanf("%d",&n);													// defining the array size
     int array[n];
@@ Line 53: / Line 53: @@
     for (int i = 0; i < n; i++)
+    {
-	   scanf("%d",&array[i]);					// Setting the array elements
+	   scanf("%d",&array[i]);										// Setting the array elements
+    }
     printf("Enter value to find\n");
-    scanf("%d", &key);							// Keying in the value which has to be searched
+    scanf("%d", &key);												// Keying in the value which has to be searched
-    pos= bin_search(array,n,key);					// Calling the Binary search function
+    pos= bin_search(array,n,key);									// Calling the Binary search function
     if(pos==0)
+    {
@@ Line 66: / Line 66: @@
     else
+    {
-	   printf("%d found at location %d.\n", key, pos);		//Printing the value fetched
+	   printf("%d found at location %d.\n", key, pos);				//Printing the value fetched
+    }
     return 0;
+}
-</pre>
+</syntaxhighlight>

← Older revision		Revision as of 00:18, 3 December 2016
Line 10:		Line 10:
	Below Image shows the formation of the algorithm in binary tree structure.		Below Image shows the formation of the algorithm in binary tree structure.
	[[File:CmpE243_F16_Binary Search Algorithm.png\|thumb\|link=File:CmpE243_F16_Binary Search Algorithm.png\|frame\|upright=0.9\|center\|Binary Search Tree]]		[[File:CmpE243_F16_Binary Search Algorithm.png\|thumb\|link=File:CmpE243_F16_Binary Search Algorithm.png\|frame\|upright=0.9\|center\|Binary Search Tree]]
		+

@@ Line 1: / Line 1: @@
 ==Binary Search==
-The Drawback of the Linear search was that, it was not efficient enough when the data set was huge. This Drawback is eliminated when Binary Search algorithm is used. But the drawback of this algorithm is that the data set has to be sorted.
+The drawback of the linear search was that, it was not efficient enough when the data set was huge. This Drawback is eliminated when Binary Search algorithm is used. But the drawback of this algorithm is that the data set has to be sorted.
 In this Algorithm the data set would be divided into 2 equal parts in every iteration till the required element is found or till the case when further equal division is not possible.
 This algorithm is similar to searching for a particular page in a book.

@@ Line 61: / Line 61: @@
     if(pos==0)
+    {
-	   printf("Search unsuccessful, %d not found.\n", key);	// If position of the searching stays at 0 element or beginning
+	   printf("Search unsuccessful, %d not found.\n", key);	        // If position of the searching stays at 0 element or beginning
+    }
     else

@@ Line 9: / Line 9: @@
 Below Image shows the formation of the algorithm in binary tree structure.
-[[File:CmpE243_F16_Binary Search Algorithm.png|thumb|link=File:CmpE243_F16_Binary Search Algorithm.png|frame|upright=0.9|left|Binary Search Tree]]
+[[File:CmpE243_F16_Binary Search Algorithm.png|thumb|link=File:CmpE243_F16_Binary Search Algorithm.png|frame|upright=0.9|center|Binary Search Tree]]
 '''Code Snippet'''
 <pre>