Binary search
Binary search is a searching algoithm for finding an elements position in a sorted array.Binary search algorithm can be implented in two ways
1.iteration method
2. recursive method
Algorithm steps
step 1. the array in which searching is to be performed
3 4 5 6 7 8 9
let x=4 be the element to be search
step 2. set the pointer low and high at the lowest and the highest position respecly
3 4 5 6 7 8 9
here 3 =low
9=high
step 3.
find the middle element mid of the array
arr[(low+high)/2]=6
3 4 5 6 7 8 9
here 6 is the mid
step 4. if x== mid ,then return mid.
else compare the element to be searched with mid
step 5 .if x>mid ,compare x with the middle element of the elements on the right side of the mid.this is done by setting low to low=mid+1
step 6.
else,
compare x with the element of the elements on the left side of mid
this is setting high to
high=mid-1
3 4 5 6 7 8 9
3=low
5=high
on the left side of the mid
step 7.
repeat steps 3 to 6 until low meets high
step 8 . x=4 is found
3 4 5
x=mid
Algorithm for iteration method
do until the pointers low and high meet each other
mid = (low+high)/2
if(x== arr[mid])
return mid
else if (x>arr[mid])
low=mid+1
else
high=mid-1
recursive method
binarySearch(arr, x, low, high)
if low > high
return False
else
mid = (low + high) / 2
if x == arr[mid]
return mid
else if x > arr[mid]
return binarySearch(arr, x, mid + 1, high)
else
return binarySearch(arr, x, low, mid - 1)
Implementation
#include <stdio.h>
int binarySearch(int array[], int x, int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main(void) {
int array[] = {3, 4, 5, 6, 7, 8, 9};
int n = sizeof(array) / sizeof(array[0]);
int x = 4;
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
return 0;
}
output:
Element is found at index 1
Process returned 0 (0x0) execution time : 0.048 s
Press any key to continue.
Comments
Post a Comment