Question

101 students won iPhone. The winners listed in sorted order. How many iterations will it take for a binary search to find a particular name on the list, in the worst case?

Answer 1

The worst case time complexity for this case will be O(log n) where n is the number of elements in the array which is 101 so it can also be written as O(log₂ 101) this logarithm has a base 2 since at each iteration in a binary search the array is divided into two halves and then by comparing the middle element with our target element we check whether they are equal or not anf if they are not equal we chose any one of the halves

so the number of iterations in worst case binary search will be :

log₂ 101=6.65 which can be rounded of to 7

   int mid = (first + last)/2;  //first stores the first element and last stores the last elemnt
   while( first <= last ){  
      if ( arr[m] < key ){  // checking whether our target element is greater to middle element if yes then the second half of array is chosen
        first = m + 1;     
      }else if ( arr[m] == key ){  // checking whether middle element is equal to target element
        System.out.println("Element is found at index: " + m);  
        break;  
      }else{  
         last = m - 1;  // else first half of the array is chosen
      }  
      m = (first + last)/2;  
   }  
   if ( first > last ){  // it means the whole array is checked
      System.out.println("Element is not found!");  
   }  
 }