Question

How to write an example of O(log n) time complexity in C

Answer 1

#include <stdio.h>

// The notation O(log n) represents logarithmic time complexity. 
// The time complexity of an algorithm grows logarithmically with the size n.
 
int binarySearch(int array[], int element, int low, int high) {
    while (low <= high) {
        int n = high - low;
        int mid = low + n / 2;
  
        if (array[mid] == element)
            return mid;
  
        if (array[mid] < element)
            low = mid + 1;
        else
            high = mid - 1;
    }
      
    return -1;
}
  
int main(void) {
    int array[] = {3, 4, 8, 9, 10, 17, 21, 28, 33, 36, 42};
    int number_to_find = 21;
  
    int index = binarySearch(array, number_to_find, 0, sizeof(array)/sizeof(array[0]));
          
    if (index == -1) 
        puts("Not found");
    else
        printf("Found at index: %d", index);
        
    return 0;
}

  
  
/*
run:
  
Found at index: 6
  
*/

 

70+ SQL courses for beginners and professionals