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