What is the runtime complexity of the following code? NumberSearch(numbers, N, key) { mid = 0; low = 0; high = N - 1; while (high = low) { mid = (high + low) / 2; if (numbers[mid] key) high = mid – 1; else return mid; } return -1; }

Question

What is the runtime complexity of the following code?

NumberSearch(numbers, N, key) {
   mid = 0;
   low = 0;
   high = N - 1;
   while (high >= low) {
      mid = (high + low) / 2;
      if (numbers[mid] < key) 
         low = mid + 1;
      else if (numbers[mid] > key) 
         high = mid – 1;
      else 
         return mid;
   }
   return -1; 
}

BlackTom AI · Accepted Answer

Binary search halves the search interval each iteration, so the loop runs in time proportional to the logarithm of N.

1. Relevant knowledge points and concepts
- This code implements binary search on a sorted array: at each iteration it compares the middle element to the key and discards half the remaining elements.
- Time complexity depends on how many times the array can be halved before the search interval is of size 1.
- Each iteration does a constant amount of work (index computations and a comparison), so total time = (number of iterations) × O(1).

2. Step-by-step reasoning
- Start with an interval of size N (low = 0, high = N−1).
- After one iteration, the interval becomes roughly N/2 (either the left half or the right half).
- After k iterations the interval size is approximately N / 2^k.
- The loop stops when the interval size ≤ 1 (no more elements to split).

3. Calculations and intermediate steps
- Solve N / 2^k ≤ 1 → 2^k ≥ N.
- Taking base-2 logarithms: k ≥ log2(N).
- Therefore the number of iterations k is O(log N). Each iteration costs O(1), so total time is O(log N).

4. Why the correct answer is correct
- Because the loop reduces the search space by a factor of two each time, the number of iterations grows logarithmically with N. Thus runtime is logarithmic in N (Θ(log N) in the worst and average cases; best case O(1) if the middle element equals the key immediately).

5. Why the other options are incorrect
- Linear: O(N) would mean examining elements one-by-one; binary search examines far fewer elements by halving each time, so it is not linear.
- Log-linear: O(N log N) implies an outer loop over N combined with a logarithmic inner cost (e.g., sorting), which this code does not do.
- Exponential: O(2^N) grows far faster and does not describe a simple halving loop.

6. Conclusion
The runtime complexity is logarithmic, which matches the provided correct answer.

What is the runtime complexity of the following code? NumberSearch(numbers, N, key) { mid = 0; low = 0; high = N - 1; while (high >= low) { mid = (high + low) / 2; if (numbers[mid] < key) low = mid + 1; else if (numbers[mid] > key) high = mid – 1; else return mid; } return -1; }单项选择题

类似问题

Binary Search Considering the following list. {12, 13, 15, 20, 23, 24, 25, 36, 40} What are the two first elements of the list that will be checked to find 25 using binary search? 1: The 1st element 2: The 2nd element

Given the following list of sorted elements, how many elements of the list will be checked to find 25 using binary search? {12, 13, 15, 20, 23, 24, 25, 36, 40}

What is the prerequisite for using binary search on a list?

Binary search can be implemented using which programming approaches?

What happens if binary search is used on an unsorted list?

In a binary search algorithm, if the middle element is greater than the target, what happens next?

Given a list of 64 elements, how many elements will be checked to look for a value that is larger than the largest value in the list using binary search?

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单