0
int binarySearch(int arr[], int left, int right, int x)
{

  while( left <= right)
  {
    int mid = (left+right)/2;
    if(arr[mid] == x)
    {
      return mid;
    }
    else if(arr[mid] > x) 
    {
      right = mid-1; 
    }
    else  
    {
      left = mid+1; 
    }
  }
  return -1;
}

when I went through this myself I got 5n+4 = O(n) but somehow it is suppose to be O(logN) which I don't understand why that's the case. 

int mean(int a[], size_t n)
{
   int sum = 0;                 // 1 step
   for (int i = 0; i < n; i++)  // 1 step *(n+1)
     sum += a[i];               // 1 step
   return sum;                  // 1 step
}

I understand that the above code reduces to 2N+3 but this is a very basic example and doesn't take much thought to understand. Will someone please walk me through the binary search version as all the sources I have encountered don't make much sense to me.

Here is a link to one of the many other resources that I have used, but the explanation as to how each statement is separated into steps is what I prefer if possible.

how to calculate binary search complexity

Code_Cuts
  • 3
  • 1
  • 5
  • How do you come at `5n+4`? – Luai Ghunim Feb 10 '18 at 21:42
  • `int binarySearch(int arr[], int left, int right, int x) { while( left <= right) // 1 step * (n+1) { int mid = (left+right)/2; // 1 step * (n) if(arr[mid] == x) // 1 step * 1 { return mid; // 1 step * (n) } else if(arr[mid] > x) // 1 step * 1 { right = mid-1; // 1 step * (n) } else // 1 step * 1 { left = mid+1; // 1 step * (n) } } return -1; // 1 step * 1 } ` – Code_Cuts Feb 10 '18 at 22:19
  • I couldn't figure out how to format it but I calculated the steps based on the examples I had. As the comments say in the second simplified example. – Code_Cuts Feb 10 '18 at 22:28

2 Answers2

2

In binary search you always reduce problem size by 1/2. Lets take an example: searching element is 19 and array size is 8 elements in a sorted array [1,4,7,8,11,16,19,22] then following will be the sequence of steps that a binary search will perform:

  1. Get the middle element index i.e. divide the problem size by 1/2.

  2. Check if element at index is greater than, less than or equal to your searching element.

    a. If equal you are done, return the index

    b. If searching element is greater, then keep looking on right half of array

    c. If searching element is less, than look on left half of array

  3. You continue step 1 and 2 until you are left with one element or you found the element.

In our example problem will look as follows:

Iteration 1: [1,4,7,8,11,16,19,22]
Iteration 2: [16,19,22]
Iteration 3: [19]

Order of complexity: O(log<sub>2</sub>(n)) i.e. log<sub>2</sub>8 = 3, which means we required 3 steps to find our desired element. Even if element was not there (i.e. in worst case) time complexity of this algorithms remains log2n.

Its important to note base of log in binary search is 2 as we are reducing problem size by 1/2, if in any other algorithm we are reducing problem size by 1/3 than its log3 but asymptotically we call it as logarithmic algorithm irrespective of its base.

Vishrant
  • 15,456
  • 11
  • 71
  • 120
0

Note: Binary search can only be done on sorted data.

Suppose i have an array of 10 elements. Binary search will split the array into two halfs, in this case 5(call it L because these are left 5 elements) and 5 (call it right because these are right 5 elements).

Suppose the element you are trying to find is greater than middle elements , in this case x > array[5] then you just ignore first 5 elements and go to last five elements.

Now you have an array of five elements(starting from index 5 to 10). Now again you will split the array into two halfs , if x > array[mid] then you ignore left whole array and if it is smaller then you ignore whole right array.

In mathematical notation you get a series like this: {n , n/2,n/(2^2) , n/(2^m)}

Now if you try to solve this: Because the highest term is n/2^m so we have n/2^m = 1 and this has a solution as log(n)

Luai Ghunim
  • 976
  • 7
  • 14