Browse Prior Art Database

Algorithm to Represent Statistical Properties of the Binary Search Technique in a Computer Simulation Program

IP.com Disclosure Number: IPCOM000074604D
Original Publication Date: 1971-May-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 2 page(s) / 21K

Publishing Venue

IBM

Related People

Dreisbach, JW: AUTHOR [+2]

Abstract

Often it is desirable to represent the performance characteristics of a binary search in a computer simulation program, without resorting to simulation of the individual events (searches) which comprise a binary search. This maybe accomplished as described below.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 78% of the total text.

Page 1 of 2

Algorithm to Represent Statistical Properties of the Binary Search Technique in a Computer Simulation Program

Often it is desirable to represent the performance characteristics of a binary search in a computer simulation program, without resorting to simulation of the individual events (searches) which comprise a binary search. This maybe accomplished as described below.

Suppose there are M elements arranged sequentially in the form a(1), a(2),..., a(j), a(j+1),...,a(m), and it is desired to locate the a element using a binary search technique. The probability density function of the number of searches required to locate the desired element will be described. From the density function, the expected number of searches and the variance can be obtained. These quantities and/or the density function may then be implemented in a simulation model, thus eliminating the need for simulating the actual steps used in a binary search procedure.

At any step in the search process, the index of the next element to be examined is given by [m--n over 2 plus n. where a(n) is the first element in the set under consideration and a(m) is the last element. The symbol "[ ]" indicates the greatest integer less than or equal to the enclosed quotient. If there are M elements and each has the same probability of being chosen, then the probability density function for the number of searches needed to locate a specific element is given by 2/k-1/ over M , for 1<k<N, f(k) = M-(2/N/-1) over M fo...