Binary Search Implementations And Common Errors
We suggest you do not use library functions for binary search as its very likely that you will be explicitly asked to implement the binary search in interviews.
Implementation of Binary Search
// binary search example in C/C++
/* here Arr is an of integer type, n is size of array
and target is element to be found */
int binarySearch(int *Arr, int n, int target) {
//set stating and ending index
int start = 0, ending = n-1;
while(start <= ending) {
// take mid of the list
int mid = (start + end) / 2;
// we found a match
if(Arr[mid] == target) {
return mid;
}
// go on right side
else if(Arr[mid] < target) {
start = mid + 1;
}
// go on left side
else {
end = mid - 1;
}
}
// element is not present in list
return -1;
}// binary search example in Java
/* here Arr is an of integer type, n is size of array
and target is element to be found */
int binarySearch(int Arr[], int n, int target) {
//set stating and ending index
int start = 0, ending = n-1;
while(start <= ending) {
// take mid of the list
int mid = (start + end) / 2;
// we found a match
if(Arr[mid] == target) {
return mid;
}
// go on right side
else if(Arr[mid] < target) {
start = mid + 1;
}
// go on left side
else {
end = mid - 1;
}
}
// element is not present in list
return -1;
}# binary search example in Python
# here Arr is an of integer type, n is size of array
# and target is element to be found
def binarySearch(Arr, n, target) :
#set stating and ending index
start, end = 0, n-1
while start <= end :
mid = (start + end) / 2
# we found a match
if Arr[mid] == target :
return mid
# go on right side
elif Arr[mid] < target :
start = mid + 1
# go on left side
else :
end = mid - 1;
# element is not present in list
return -1
Walkthrough Examples :
