Searching Algorithm 2: Binary search

In this chapter we shall learn about below topics:

Binary search is a simple search technique that works on sorted array, either it can be ascending or descending.

Below are the steps to perform binary search:

1. Binary search can be similar to searching a word in a dictionary. We open the book in the middle and check if the name is found.

2. If the word is not found, depending upon the results we get we tend to move forward or backward.

3. If the word is found, then we take the meaning of that word.

Program design is very simple.

1. We consider first element as low and the last element as high. i.e. the array should be sorted.

2. We get the index of middle element by using below formula:
    a. mid = (low + high) / 2.

3. Then we compare the value of middle element with the key as shown below:
    a. If (key == a[mid]) return mid.

4. Suppose if the key is not found in that index, we check if the key is lower or higher than the mid value. Suppose if the key value is lower, then we change the high to the mid element and repeat step 1.

If(key < a[mid])
    High = mid -1
Else
    Low = mid + 1

Basically from the above explanation, there will be 3 cases.

Case 1: When the key  == array[mid]. In this case we exit the loop

Case 2: When key > array[mid]. In this case we move towards right half of the array.

Case3: When key < array[mid]. In this case we move towards left half of the array.

Consider the sorted array

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
key = 2

First Pass: 
[8/2] = 4
is arr[4] == 2 ? No, and 2 < 5. Hence discard right half and move towards left half.

Second Pass: 
[3/2] = 2
is arr[2] == 2 ? No, and 2 < 3. Hence discard right half and move towards left half.

Third Pass: 
[1/2] = 1
is arr[1] == 2 ? Yes, hence our result.

#include<stdio.h>
 
void binary_Search(int *array, int len, int key)
{
 
	int i = 0;
 
	int min_index = 0;
	int max_index = len-1;
 
	while(min_index <= max_index) 
	{
		// calculate the mid index
		int mid = (min_index + max_index) / 2;
		printf("mid = %d\n",array[mid] );
		// check if we get the key
		if(array[mid] == key) 
		{
			printf("Key has been found\n");
			return; 
		}
 
		// traverse in the right side
		else if(array[mid] < key) 
		{
			min_index = mid + 1;
		}
		// traverse in the left side
		else 
		{
			max_index = mid - 1;
		}
	}
 
	printf("Not able to find key\n");
 
}
 
int main()
{
	int arr[5] = {10, 30, 45, 48, 78};
 
	int arrayLen = 5;
 
	int key = 45;
 
	int key_2 = 34;
 
//successful search
	binary_Search(arr,arrayLen, key);
 
//key not found case
	binary_Search(arr,arrayLen, key_2);
 
return 0;
}

Run time at worst case for binary search:

In the worst case, we reduce from n to n/2

n/2 to n/4

n/4 to n/8, we reduce till we arrive at 1.

Hence n/ 2^k = 1

K = log n.