Binary Search Implementation

Binary Search Code in C

#include 

// Binary search - search for element in sorted array
// Set start to beginning index of array and end to last index of array
// Check if middle index is equal to target
// If target is lower, set end to middle
// If target is higher, set start to middle
// Repeat until middle is equal to target
int binarySearch(int *arr, int target, int len, int tshow) {
	int numOfOperations = 0;
	int start = 0;
	int end = len;
	int mid = (int)(len/2);
	while ((end - start) > 1) {
		if (target == arr[mid]) {
			if (tshow) {
				printf("Size of data: %d, num of operations (worst-case): %d.\n", len, numOfOperations);
			}
			return mid;
		} else if (target > arr[mid]) {
			start = mid;
		} else {
			end = mid;
		}
		mid = (int)((start + end)/2);
		numOfOperations += 1;
	}
	if (tshow) {
		printf("Size of data: %d, num of operations (worst-case): %d.\n", len, numOfOperations);
	}
	return -1;
}

int main(int argc, char* argv[]) {
	int array[] = {3, 4, 6, 15, 18, 27, 34, 48, 53, 58, 67, 74, 96, 100, 140, 176, 213, 270, 376, 467, 679, 1025};
	int num = 270;
	int idx = binarySearch(array, num, sizeof(array)/sizeof(*array), 0);
	if (idx == -1) {
		printf("Value not found.\n");
	} else {
		printf("%d found at index %d.\n", num, idx);
	}
	num = 3000;
	idx = binarySearch(array, num, sizeof(array)/sizeof(*array), 1);
	// Size of data: 22, num of operations (worst-case): 5. 
	// log2(22) = 4.45
	// Time complexity: O(log2(n))
}

Explanation of the Code

Main Function

int array[] = {3, 4, 6, 15, 18, 27, 34, 48, 53, 58, 67, 74, 96, 100, 140, 176, 213, 270, 376, 467, 679, 1025};
int num = 270;

Initialize the array and the value (number) to be searched for. Note: The array is already sorted since binary search requires the array to be in order.

int idx = binarySearch(array, num, sizeof(array)/sizeof(*array), 0);

The binarySearch function takes the array, the value to be searched for and the length of the array and returns the index of the element where the value is stored in the array, the index is stored in the variable, idx.

if (idx == -1) {
        printf("Value not found.\n");
} else {
        printf("%d found at index %d.\n", num, idx);
}

If idx is equal to -1, the binarySearch function returned -1, meaning the number is not in the array.

Since -1 is not an index number, "Value not found." is printed instead.

If idx is any number other than -1, the binarySearch successfully returned the index value of the number and the index can be printed.

num = 3000;
idx = binarySearch(array, num, sizeof(array)/sizeof(*array), 1);

Test binarySearch with number that is not in the array to see worst-case number of operations. Pass 1 as final argument instead of 0.

Binary Search Function

int binarySearch(int *arr, int target, int len, int tshow) {

The binarySearch function takes array, target element (value to be found), length of array and tshow - whether to display number of operations or not.

int start = 0;
int end = len;
int mid = (int)(len/2);

start and end are the indices of the array bounding the range of elements possibly equalling the target. At the start of the algorithm the range includes all elements (start is the index to the first element and end is the index of the last element).

mid is the index between start and end. It is the value being compared in each iteration.

while ((end - start) > 1) {

Repeat narrowing down array until end and start indices have a difference of 1.

if (target == arr[mid]) {
	if (tshow) {
		printf("Size of data: %d, num of operations (worst-case): %d.\n", len, numOfOperations);
	}
return mid;

Check if the median value of the values between indices start and end is equal to, greater than, or less than target.

If they are equal return the index (mid).

} else if (target > arr[mid]) {
	start = mid;

If target is greater, mid

	} else {
		end = mid;
	}

	mid = (int)((start + end)/2);
	numOfOperations += 1;
}

Visualization of Binary Search

0