Data Structures and Algorithms - Understanding Binary Search - Day 2

Let’s look at the binary saearch code again

#include <stdio.h>

int main(){
    int a[10],x, start=0, end=9, middle;
    middle = (start + end) / 2;
    printf("Enter the elements of the array: ");
    for(i = 0; i<10; i++){
        scanf("%d",&a[i]);
    }
    printf("Enter the element to search: ");
    scanf("%d",&x);
    //find element
    while(start <= end){
        if(x < a[middle]){
            end = middle - 1;
        }
        else if(x > a[middle]){
            start = middle + 1;
        }
        else{
            printf("The element is found at index %d", middle);
        }
        middle = (start + end) / 2;
    }
    if(start > end){
        printf("Element not found");
    }
    return 0;
}

Let’s take an example -

a = {1,2,3,5,7,9,10,12,14,15,16}
start = 0
end = 9
middle = (0+9)/2 = 4.5 (let's take the floor value) = 4
x = 10 (The element we are trying to find)

As at this point start (0) <= end (9) is true, we get in the loop where we have a[middle] = 7.

Now 10 > 7 so condition 2 is satisfied so we set start = middle + 1 = 4 +1 = 5

So at the end of this loop -

start = 5
end = 9
middle = (5+9)/2 = 7

Now it still satisfie start(5) <= end(9). So we get to the middle element a[middle] = 12

Now 10 < 12 so condition 1 is satisfied so we set end = middle - 1 = 7 - 1 = 6

So at the end of this loop -

start = 5
end = 6
middle = (5+6)/2 = 5.5 (floor the value)= 5

Now it still satisfie start(5) <= end(6). So we get to the middle element a[middle] = 9

Now 10 > 9 so condition 2 is satisfied so we set start = middle + 1 = 5 + 1 = 6

So at the end of this loop -

start = 6
end = 6
middle = (6+6)/2 = 6

Now it still satisfie start(6) <= end(6). So we get to the middle element a[middle] = 10

Now 10=10 satisfies condition 3 so we print Element found at index 6 (middle)