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:
- 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.
- If the word is not found, depending upon the results we get we tend to move forward or backward.
- If the word is found, then we take the meaning of that word.
Program Design:
Program design is very simple.
- We consider first element as low and the last element as high. i.e. the array should be sorted.
- We get the index of middle element by using below formula:
- mid = (low + high) / 2.
- Then we compare the value of middle element with the key as shown below:
- If (key == a[mid]) return mid.
- 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
Understanding Binary Search with the help of an example:
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.
Example:
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.
C code for binary search:
#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.
Hence at worst case, it will take [log n].
Further Reading:
Praveen
please share some java programming with data structure