Embedded Files
Check The Programming Section
A binary search, also known as a half-interval search, is an algorithm used in computer science to locate a specified value (key) within an array. For the search to be binary, the array must be sorted in either ascending or descending order. To search an item from a sorted array, we need three indexes of the array as left, right, and mid.
A sorted array of 10 items
Consider the sorted array listed above as num. The array num has 10 items in ascending order (smallest to largest). Before start searching, we needs to initilaize the three indexes as follows:
left = 0;
rigth = sizeof num/sizeof num[0] - 1;
mid = (left + right)/2;
In binary search, searched item always compared with the middle element of the array. If the searched item is same as num[mid], then mid index is returned as the location of the item. Else seraching is continued with the condition left<=right. Once left and right indexed crossed each other, it means seaching item is not present in the array. In the second pass of searching, there will two scenario:
Searching an item 5 (less than current num[mid])
In this case, left index will remain in its position, because 5 is present at the left side of mid value (num[mid] = 34). So, array is partitioned and the right, and mid index is updated as follows:
Searching an item which is less than mid indexed value
Searching an item value which is greater than mid
right = mid - 1;
mid = (left + right)/2;In PASS-2 it is found that the new mid indexed value is equal to the searching item 5. So the searching is stoped here.
2. Searching an item 91 (greater than current num[mid])
In this case, right index will remain in its position, because 91 is present at the right side of mid value (num[mid] = 34). So, array is partitioned and the left, mid index is updated as follows:
left = mid + 1;
mid = (left + right)/2;
To search 91, algorithm takes 3 passes (iteration). In the second pass left and mid is updated and after comparison it is found that, num[mid] = 89 is not equal to search item 91 and 91 is greater than current mid value. So the array is further partitioned for another pass and in the third pass, searched item is found at the mid position 8 and algorithm stops searching.
If you put everything in one picture, it will be as follows:
Two searching in one frame. Red colored item considered the search item
The required source code of Binary Search using an array and function is (edit and try)
#include<iostream>
using namespace std;
int binarySearch(int num[], int size, int searchItem){
int left = 0;
int right = size-1;
int mid = (left+right)/2;
while(left<=right){
if(num[mid]==searchItem) return mid;
else if(searchItem<num[mid]){
right = mid-1;
mid = (left+right)/2;
}
else{
left = mid+1;
mid = (left+right)/2;
}
}
return -1;
}
int main(){
int num[] = {-3, 5, 12, 23, 34, 45, 76, 89, 91, 94};
int size = sizeof num/sizeof num[0];
int searchItem;
cout<<"Enter an item to be search ";
cin>>searchItem;
int index = binarySearch(num, size, searchItem);
if(index==-1){
cout<<searchItem<<" is not found in the array";
}
else{
cout<<searchItem<<" is found at index "<<index;
}
}
Page updated
Google Sites
Report abuse