Monday, 26 February 2018

Binary search algorithm in data structures using C

Binary search algorithm in data structures

Binary search

Binary search is a search algorithm that works with the concept of divide and conquer. It is a fast search algorithm with the time complexity of O(log n). It requires that the keys in the array should be stored in a sorted order.
Let us assume an array a[] of n elements and the key k to be searched among them. The algorithm finds the middle element of array a[] and compares with the key to be found. If they match, then return the index as result. If not, algorithm divides the array into two halves on the middle element and based on the search key value it searches in one of the sub-arrays. If the key value is smaller than the middle element, then search continues with left sub-array otherwise with the right sub-array. The array is sub-divided recursively until the element is found or the entire array is scanned.

Algorithm:
Step 1: Read the array of keys and the key to be searched as input.
Step 2: Find and compare the middle element of the array with the key to be searched.
Step 3: If the middle matches with the key, then the middle index is returned as result and closes the program.
Step 4: If the middle does not match with the key to be searched, then the algorithm divides the array into two halves.
Step 4a: If the key is greater than middle element, the algorithm omits the lower half of the array and considers only the higher half.
Step 4b: If the key is smaller than the middle element, it considers the lower half. And go to step 2.
Step 5: Repeat steps 2 to 4b until the element is found or all the elements in the array are scanned.

Pseudocode:
int binarySearch(int a[], int low_index, int high_index, int key_to_find)
{
int mid_index;
   While (low_index <= high_index)
   {
     mid_index = (low_index + high_index)/2;
     if(a[mid_index] < key_to_find)
         low_index = mid_index + 1;
     else if(a[mid_index] > key_to_find)
         high_index = mid_index - 1;
     else
         return mid_index;
     }
   }
   return -1;
 }

Algorithm Description:
Algorithm / Pseudocode
Description
1: bSearch (a[], low_index, high_index, key_to_find)
2:  {
3:  int mid_index;
4:  while (low_index <= high_index)
5:  {
6:     mid_index = (low_index + high_index)/2;
7:     if(a[mid_index] < key_to_find)
8:         low_index = mid_index + 1;
9:     else if(a[mid_index] > key_to_find)
10:         high_index = mid_index - 1;
11:     else
12:         return mid_index;
13:   }
14:   return -1;               
15: }



4: if left most index of the array is smaller/equal
to right most index then loop
6: find the middle index
7: if the element stored in middle index < key
8: new low index will be middle + 1 (right half)
9: if middle element > key
10: new high index will be middle -1 (left half)

12: if 7 and 9 are invalid, our result is middle.

14: if the key not found in array return -1


************



Binary search algorithm in data structures
How does binary search algorithm work
Implementation of binary search algorithm








No comments:

Post a Comment

SQL exercises for beginners one

SQL Exercises for Beginners / Simple SQL Exercises with Answers / Solved SQL exercises / SQL solved exercises with simple conditions / So...