Binary Search Let A[1...n]be a sequence of n elements.Consider the problem of determining whether a given element xis in A
Binary Search ◼ Let A[1…n] be a sequence of n elements. Consider the problem of determining whether a given element x is in A
Binary Search Example: A[1..14]=1457891012152223273235 X=22 Does X exist in A?How many comparisons do you need to give the answer?
Binary Search Example: A[1…14]=1 4 5 7 8 9 10 12 15 22 23 27 32 35 x=22 Does X exist in A? How many comparisons do you need to give the answer?
Binary Search Inputs:(1)An array A[1...n]of n elements sorted in nondecreasing order;(2)x, Output:jif x=A],and 0 otherwise; 1.lowk-1;high-n;衣-0； ■ 2.while (low<high)and (0) ■ 3. midk(low+high)/2; ■ 4. if x=A[mid]then mid; 5. else if x<A[mid]then highmid-1; ■ 6. else low-mid+1; 7.end while; 8.return
Binary Search ◼ Inputs: (1) An array A[1…n] of n elements sorted in nondecreasing order; (2) x; ◼ Output: j if x=A[j], and 0 otherwise; ◼ 1. low1; highn; j0; ◼ 2. while (lowhigh) and (j=0) ◼ 3. mid(low+high)/2; ◼ 4. if x=A[mid] then jmid; ◼ 5. else if x<A[mid] then highmid–1; ◼ 6. else lowmid+1; ◼ 7. end while; ◼ 8. return j;
Binary Search What's the performance of the algorithm Binary Search on a sorted array of size n? What's the minimum number of comparisons we need and in which case it will happen? v What's the maximum number of comparisons we need and in which case it will happen?
Binary Search ◼ What’s the performance of the algorithm Binary Search on a sorted array of size n? ✓ What’s the minimum number of comparisons we need and in which case it will happen? ✓ What’s the maximum number of comparisons we need and in which case it will happen?
Binary Search The number of comparisons performed by the algorithm Binary Search on a sorted array of size n is at most Llog n+1
Binary Search ◼ The number of comparisons performed by the algorithm Binary Search on a sorted array of size n is at most log n+1