Finding number of comparisons

Redowan K. Shajib :

I'm trying to track the number of key comparisons in this binary search code. The comparison result should be around 17 for an array size of 2^16. Can you explain why I'm getting 33?

public class AdvancedBinarySearch {

    int count = 0;

    // Returns location of key, or -1 if not found 
    int AdvancedBinarySearch(int arr[], int l, int r, int x) {
        int m;

        while (r - l > 1) {
            count++;
            m = l + (r - l) / 2;
            if (arr[m] <= x) {
                l = m;
                count++;
            } else {
                r = m;
                count++;
            }
        }

        if (arr[l] == x) {
            count++;
            return l;
        }

        if (arr[r] == x) {
            count++;
            return r;

        } else {
            count++;
            return -1;

        }
    }

    public void setCount(int i) {
        this.count = i;
    }
}
Jyon Nyre :

Your code is counting the if (arr[m] <= x) comparison twice. if you remove the count++ from below l = m and also from below r = m, this will no longer happen.

I have tested this before and after this change with a search for 189 in an array of the integers from 0 to 65535. This array had a size of 2^16 and before the change, 33 comparisons were counted and after the change, 17 comparisons were counted, so I think this change does what you want it to do.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

Number of comparisons in duplicates finding algorithm

Finding the total number of elements in list, comparisons and swaps needed to sort the numbers list using selection sort

Insertion sort, number of comparisons

Finding the asymptotic amount of comparisons performed by an algorithm

Number of comparisons in quick sort variation

Formula for determining number of comparisons in a sort?

Heap Sort Algorithm number of comparisons

Сounting the number of comparisons and permutations in heapsort

Counting number of comparisons in shell sort

How to count the number of comparisons in this algorithm?

Number of comparisons for different lists in sorting algorithms

Number of comparisons and swaps of the heap sorting method

Java binary search count number of comparisons

properly count the number of insertion sort comparisons

Binary Search: Number of comparisons in the worst case

Bubble sort the total number of comparisons and swaps

Number of swaps and comparisons in Shaker/Cocktail sort -Java

What is the maximum number of comparisons to heapify an array?

Average number of comparisons searching a list of size n?

Number of key comparisons for best case in MergeSort

Is there a known algorithm for simplifying a boolean expression with number comparisons?

Python: Calculate total number of comparisons to find a match

Finding a number at a particular digit in a number

Finding the number of views of a website

Finding the digital root of a number

Finding the number of Polysyllables in java

finding the nearest number in an array

Finding the number of lists in a tuple

Finding the Number of Quadruples