Binary Search

It is search algorithm that finds value within the sorted array.

It compares the target value to the middle element of array.

If they are not equal than, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again repeating the same process until the target value is found.

If the search ends with the remaining half being empty, the target is not in the array.

---

Example:

array[]={2, 5, 8, 10, 16, 23, 39, 56, 72, 95}

key is 23

L=0 1 2 3 M=4 5 6 7 8 H=9

2 5 8 10 16 23 39 56 72 95

Now as 23>16

take 2nd half

0 1 2 3 4 L=5 6 M=7 8 H=9

2 5 8 10 16 23 39 56 72 95

Now as 23<56

take 1st half

0 1 2 3 4 L=5,M=5 H=6 7 8 H=9

2 5 8 10 16 23 39 56 72 95

---

Implementation using C: (Recursion)

#include <stdio.h> 
  
int binary_Search(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        // If the element is present at the middle 
        if (arr[mid] == x) 
            return mid; 
  
        // If element is smaller than mid, then 
        // it can only be present in left subarray 
        if (arr[mid] > x) 
            return binary_Search(arr, l, mid - 1, x); 
  
        //else element can only be present in right subarray 

        return binary_Search(arr, mid + 1, r, x); 
    } 
    // when element is not present in array 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 20, 30, 40, 100, 400 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int x = 100; 
    int result = binary_Search(arr, 0, n - 1, x); 
    (result == -1) ? printf("Element is not present in array") 
                   : printf("Element is present at index %d", 
                            result); 
    return 0; 
} 

Output:
Element is present at index 3

---

(Iterative)

#include <stdio.h> 

int binary_Search(int arr[], int l, int r, int x) 
{ 
    while (l <= r) { 
        int m = l + (r - l) / 2; 
  
        // Check if x is present at mid 
        if (arr[m] == x) 
            return m; 
  
        // If x greater, ignore left half 
        if (arr[m] < x) 
            l = m + 1; 
  
        // If x is smaller, ignore right half 
        else
            r = m - 1; 
    } 
  
    // element was 
    // not present 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 20, 30, 40, 100, 400 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int x = 100; 
    int result = binary_Search(arr, 0, n - 1, x); 
    (result == -1) ? printf("Element is not present"
                            " in array") 
                   : printf("Element is present at "
                            "index %d", 
                            result); 
    return 0; 
} 

Output:
Element is present at index 3

---

Miscellaneous:

Time Complexity for best case: O(1) . For more click here.

Space complexity: O(1) in case of iterative and O(logn) for recursion.

Follow for more tech blogs #programmersdoor #searching #datastructures