Exercise 2: Binary Search Binary search is an efficient algorithm for finding th

Question

Exercise 2: Binary Search Binary search is an efficient algorithm for finding the location of a value in a sorted array. Given a key value to be found, the algorithm first examines the middle element of the array. Say the middle element's value is less than the key value, and assuming the array is sorted in ascending order, then the key can only be in the upper part of the array. The process is repeated on the upper part of the array, examining its middle element and comparing to the key value to be found. At each step, the length of the sub-array being examined shrinks by (approximately) a factor of 2, until the key is found (it is the middle element of the sub-array being examined) or the sub-array size has shrunk to zero (in which case the key value is not in the array). Example 1: Find key 21 Step #1: compare middle element to key-key > mid | 2 | 3 | 6 | 9 |10| 19| 20121| 32 20 21 32 39 10 19 2021 32 6 9 19 | Step #2 : compare middle element to key key , mid | Step #3: compare middle element to key: key-mid 2 Example 2: Find key 9 Step # 1: compare middle element to key: key mid 2 · 3 6 | 9 | 10-9 , 20 | 2 32 Step #3 : compare middle element to key keys-mid | 2 | 3 | 6-10 | 19 | 20 | 21 | 32 Task: Write an implementation of Binary Search in Java that takes an array of integers (already sorted in ascending order) and a key value to be found and returns the index of the key value in the array. If the key is not found then return -1 public static int findIndex0f(int key, int[] a) { · } It is possible to implement this method using 8 Java statements. Q. What is the average time complexity of the Binary Search algorithm? If the input array were not pre-sorted then we could not use Binary Search. What time complexity would this unsorted search problem have?

Explanation / Answer

Code:

public class BinarySearch
{
    // Returns indekey of key if it is present in arr[], else
    // return -1
    public static int binarySearch(int key,int a[])
    {
        int l = 0, r = a.length - 1;
        while (l <= r)
        {
            int m = l + (r-l)/2;

            // Check if key is present at mid
            if (a[m] == key)
                return m;

            // If key greater, ignore left half
            if (a[m] < key)
                l = m + 1;

            // If key is smaller, ignore right half
            else
                r = m - 1;
        }

        // if we reach here, then element was not present
        return -1;
    }

    // Driver method to test above
    public static void main(String args[])
    {
        BinarySearch ob = new BinarySearch();
        int a[] = {2, 3, 4, 10, 40};
        int n = a.length;
        int key = 0;
        int result = ob.binarySearch(key,a);
        if (result == -1)
            System.out.println("Element not present");
        else
            System.out.println("Element found at indekey "+result);
    }
}

Explanation: Already mentioned in the problem statement

Output

For key=10, ELement found at index 3

Post next question as a different question

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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