Introduction to Algorithms Hint: Procedure BINARY-SEARCH takes a sorted array A,

Question

Introduction to Algorithms

Hint: Procedure BINARY-SEARCH takes a sorted array A, a value v, and a range [low. . high] of the array, in which we search for the value v. The procedure compares v to the array entry at the midpoint of the range and decides to eliminate half the range from further consideration.

Hint: Consider both iterative and recursive versions, each of which returns either an index i such that A[i] = v, or NIL if no entry of A[low . . high] contains the value v. The initial call to either version should have the parameters A, v, 1, n, i.e., BINARY-SEARCH(A, v,low, high).

Please type your responses to the questions. Do not provide handwritten solutions for this problem. Include the Java source code for this problem.

Explanation / Answer

Pseudocode for Binary Search

Declare array A[]
Enter n values in A[] in sorted order
Input x (to be found)
Declare pos
pos = BinarySearchRecursive(A,x,1,n) or BinarySearchIteraive(A,x,0,n-1)

if pos == -1
   output "Not found"
else
   output pos

BinarySearchRecursive(A,num,low,high)

    Declare mid
    if (high >= low)    // if the upper limit of the array is more than or equal to the lower limit
       mid = low + (high - low)/2     // calculate the mid position of the array
       if (A[mid] = x)                   // if the element at the mid position = x then return the position
          return mid
       if (A[mid] > x)                       // if A[mid] > x , then we will go to the first half
          return BinarySearchRecursive(A,x,low,mid-1)  
       else                                          //if A[mid] < x , then we will go to the second half
          return BinarySearchRecursive(A,x,mid+1,high)

    return -1

BinarySearchIterative(A,num,low,high)

    Declare mid
    Loop: (low <= high)              //if the upper limit of the array is more than or eqiual to the lower limit
       mid = low + (high - low)/2 // calculate the mid position of the array
       if (A[mid] = x)                 // if the element at the mid position = x then return the position
          return mid
       if (A[mid] > x)            // if A[mid] > x , then we will go to the first half   
          low = mid + 1
       else                     //if A[mid] < x , then we will go to the second half
         high = mid -1
    ends
    return -1

Java Source Code

class BinarySearch
{
    public int binarySearchRecursive(int arr[], int x,int l, int r)
    {
        if (r>=l)                     //if the upper limit of the array is more than or equal to the lower limit
        {
            int mid = l + (r - l)/2;

             if (arr[mid] == x)        // if the element at the mid position = x then return the position
               return mid;

            if (arr[mid] > x)                // if A[mid] > x , then we will go to the first half
               return binarySearch(arr, x,l, mid-1);
            else                           //if A[mid] < x , then we will go to the second half
             return binarySearch(arr, x,mid+1, r);
        }

        return -1;
    }
    public int binarySearchIterative(int arr[], x,int l, int r)
    {
    while (l <= r)                  //if the lower limit of the array is less than or equal to the lower limit
    {
        int m = l + (r-l)/2;       
        if (arr[m] == x)              // if the element at the mid position = x then return the position
            return m;
        if (arr[m] < x)              // if A[mid] < x , then we will go the second half
            l = m + 1;
        else
            r = m - 1;            //if A[mid] > x , then we will go the first half
    }
    return -1;
    }
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.