Suppose we have an integer array A = [-1, 2, 3, 4, 7, 9, 10] and we perform a binary search-as implemented below-on A for the number -1. How many iterations of the while loop will occur in thi process? public static > int binarySearch (E key, E[] array) { int low 0, high = array.length - 1; while (low <= high) { } int mid= low + (high low) / 2, result = key.compareTo(array[mid]); if (result == 0) { return mid; } if (result < 0) { high = mid - 1; } else { low mid + 1; } return -low - 1;
Suppose we have an integer array A = [-1, 2, 3, 4, 7, 9, 10] and we perform a binary search-as implemented below-on A for the number -1. How many iterations of the while loop will occur in thi process? public static > int binarySearch (E key, E[] array) { int low 0, high = array.length - 1; while (low <= high) { } int mid= low + (high low) / 2, result = key.compareTo(array[mid]); if (result == 0) { return mid; } if (result < 0) { high = mid - 1; } else { low mid + 1; } return -low - 1;
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
![Certainly! Here is the transcribed content suitable for an educational website, along with a detailed explanation of the code:
---
**Binary Search in an Integer Array**
Suppose we have an integer array \( A = [-1, 2, 3, 4, 7, 9, 10] \) and we perform a binary search—using the implementation shown below—on \( A \) for the number \(-1\). How many iterations of the while loop will occur in this process?
```java
public static <E extends Comparable<E>> int binarySearch(E key, E[] array) {
int low = 0, high = array.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
result = key.compareTo(array[mid]);
if (result == 0) {
return mid;
}
if (result < 0) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -low - 1;
}
```
---
**Explanation of the Code:**
This code implements a generic binary search algorithm, which can be executed on any array of objects that implement the `Comparable` interface. The key steps are:
1. **Initialization:**
- `low` is initialized to 0, meaning it starts at the beginning of the array.
- `high` is initialized to the last index of the array (`array.length - 1`).
2. **While Loop:**
- The loop continues as long as `low` is less than or equal to `high`.
- `mid` is calculated as the middle index of the current range (`low` to `high`).
3. **Comparison:**
- `result = key.compareTo(array[mid])` compares the key to the middle element.
- If `result` is 0, the key is found at index `mid`.
- If `result` is negative, the key is in the lower half, so `high` is adjusted to `mid - 1`.
- If `result` is positive, the key is in the upper half, so `low` is adjusted to `mid + 1`.
4. **Return Value:**
- If the key is found, the method returns its index.
- If not](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F080bcca4-64d9-46db-946c-9e6ea13ee4b4%2F1334cc7f-ad0d-4a17-94fd-26ee276cde7a%2Famdvsf5_processed.jpeg&w=3840&q=75)
Transcribed Image Text:Certainly! Here is the transcribed content suitable for an educational website, along with a detailed explanation of the code:
---
**Binary Search in an Integer Array**
Suppose we have an integer array \( A = [-1, 2, 3, 4, 7, 9, 10] \) and we perform a binary search—using the implementation shown below—on \( A \) for the number \(-1\). How many iterations of the while loop will occur in this process?
```java
public static <E extends Comparable<E>> int binarySearch(E key, E[] array) {
int low = 0, high = array.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
result = key.compareTo(array[mid]);
if (result == 0) {
return mid;
}
if (result < 0) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -low - 1;
}
```
---
**Explanation of the Code:**
This code implements a generic binary search algorithm, which can be executed on any array of objects that implement the `Comparable` interface. The key steps are:
1. **Initialization:**
- `low` is initialized to 0, meaning it starts at the beginning of the array.
- `high` is initialized to the last index of the array (`array.length - 1`).
2. **While Loop:**
- The loop continues as long as `low` is less than or equal to `high`.
- `mid` is calculated as the middle index of the current range (`low` to `high`).
3. **Comparison:**
- `result = key.compareTo(array[mid])` compares the key to the middle element.
- If `result` is 0, the key is found at index `mid`.
- If `result` is negative, the key is in the lower half, so `high` is adjusted to `mid - 1`.
- If `result` is positive, the key is in the upper half, so `low` is adjusted to `mid + 1`.
4. **Return Value:**
- If the key is found, the method returns its index.
- If not
Expert Solution
Step 1
Binary search works on the divide and conquer principle.
In this algorithm the list is divided into two halves, and the search element is compared with the middle element of the list.
If the match is found then, the index of the middle element is returned.
Otherwise,
If the search element is greater than the middle element, we search in the upper sub-array.
If the search element is less than the middle element, we search in the lower sub-array.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education