# Binary Search

Assume that I am going to give you a book. This time the book will have ordered page numbers unlike previous scenario (Linear search) .

#### Example

First page number as 1,

Second page number as 2,

And so on.

#### What will you do if you ask to find page number 67.

Since the page numbers are ordered in ascending, we can do something like below,

1.Open the center page of the book.

2.if the page number is equal to 67. We are done

Otherwise,

3.if

The page number is less than 67. (say 62)

You can leave the left part of the book which will have the page number from 1 to 62.

Follow the step 1 with the right part of the book. In this case starting page will be 63 (center + 1)

4.else

The page number is greater than 67. (say 75)

You can leave the right part of the book which will have the page number from 75 to end of the book.

Follow step 1 with the left part of the book. In this case ending page will be 74 (center - 1)

5.Do the above process until we find page number 67 or run out of page.

#### Binary Search: Found Case

#### Binary Search: Not Found Case

Here every time we are deciding either select left side or right side. Hence, it is called as binary search.

If we want to do binary search, the array should be in sorted order.

## Binary Search Program in c

Example

/* * Program: Binary Search * Language: C */ #include<stdio.h> //size of the array #define SIZE 8 /* * It will return 1, if search found * Otherwise it will return 0 */ int BinarySearch(int arr[],int start, int end, int key) { int mid; //do till valid range while(start <= end) { //find mid index mid = (start + end) / 2; //if arr[mid] is equal to key, search found if(arr[mid] == key) return 1; /* * if key is greater than arr[mid], skip left side array. * move the starting position to mid + 1 index */ if(arr[mid] < key) start = mid + 1; else /* * skip right side array. * move end position to mid - 1 index */ end = mid - 1; } /* * Out of the loop * Which means Key not present in the array, so return 0. */ return 0; } int main() { //sorted array int page_number[SIZE] = {10,23,45,70,90,100,111,123}; //search found case int key = 45; if(BinarySearch(page_number,0,SIZE - 1, key) == 1) printf("Search Found\n"); else printf("Search Not Found\n"); //search not found case key = 150; if(BinarySearch(page_number,0,SIZE - 1, key) == 1) printf("Search Found\n"); else printf("Search Not Found\n"); return 0; }