Question
6. (6 points) Let A[1..n] be an array containing n distinct integers sorted in increasing order, where n 1. The following algorithm from page 364
6. (6 points) Let A[1..n] be an array containing n distinct integers sorted in increasing order, where n 1. The following algorithm from page 364 of the text determines if a query integer x is in A; it returns the position of x in A if x is present and returns zero otherwise. The initial call is Binary-Search(1, n, x).
1. Binary-Search(i,j,x) // Search subarray A[i..j] for x, 1 <= i <= j <= n
2. m <- floor((i+j)/2)
3. if (x = A[m]) then return(m)
4. else if (x < A[m] and i < m) then return(Binary-Search(i,m-1,x))
5. else if (x > A[m] and j > m) then return(Binary-Search(m+1,j,x))
6. else return(0)
7. end
Let P(s) be the assertion that when presented with a subarray A[i..j] of size s = j i + 1, Binary-Search(i, j, x) returns the position of x in A[i..j] if x is present in the subarray and returns zero otherwise, 1 i j n. Use Strong Induction to prove that P(s) is true for s 1. Similar to recursive linear search (discussed in class) consider separately the cases where x is present/not present in the subarray being searched (A[i..j] here).
The question requires using Strong Induction so please have an answer using strong induction
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started