Talk:Binary search
Definition Clarification?
http://www.nist.gov/dads/HTML/suffixarray.html
The reason I bring this up is because the opening definition of binary_search is because it doesn't include a clear definition "that characteristic" used by the "sort algorithm".The charicteristic used would be the order of the data, or the orderability of the data. [E.g. a "recent changes" page can be ordered alphabetically, or chronologically. This type data two inherently sequential properties, alpha and chron., both linear arrays] I'm neither a programmer nor mathematician....=/ Suffix array is something special, too. more on that
Posted in wiki: In computer science, binary search or binary chop is a search algorithm for finding a particular value in a list of data. A divide and conquer algorithm, binary search requires random access to the data being searched, the ability to quickly get the kth item in the list. In its simplest form, binary search assumes the data is sorted (usually by a sort algorithm) and takes advantage of that characteristic.
http://www.nist.gov Definition: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty. -links to- [is an example of a:]
dichotomic search definition: Search by selecting between two distinct alternatives (dichotomies) at each step.
Data Structures, Algorithms Binary Search Algorithm
This Binary Search Algorithm uses recursive subdivisions of an array to perform a search. Enter the size of the array in the text field, and click the "Create" button. The array is created with randomly generated numbers. Now, input a search key in the text field, and click the "Search" button. http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/BSearch.html
These two definitions use the term ARRAY.
Answers.com clears this up:
ARRAY:
- Mathematics.
1. A rectangular arrangement of quantities in rows and columns, as in a matrix. 2. Numerical data linearly ordered by magnitude.
Pseudo code change
I changed the pseudocode since it was incorrect.dze27
Pseudocode:
function binary-search(L,V)
set start = 1
set end = N
repeat while start <= end
set middle = (start + end) div 2
if V = L[middle]
return success
else-if V < L[middle]
set end = middle - 1
else-if (V > L[middle])
set start = middle + 1
end-if
end-repeat
return failure
end-function
Notes:
div is integer division (discard any remainder)
In practice, the non-recursive algorithm would be implemented with some minor changes: Robocoder 15:02, 12 November 2005 (UTC)
- To avoid overflowing (e.g., left+right > maxint), calculate:
mid := floor(left+(right-left)/2)
- Searching the top half of the array is implied and does not require the conditional test:
if value > a[mid]
Bridging ideas
Has anyone else noticed that the part with the example of guessing numbers between 1-16 and the part with the pseudocode etc, aren't very well connected? Someone who don't already know what binary search is, and how it works, might not make the connection?
Anyone have any ideas how to express how the _algorithm_ for 'guessing' the right number in the 'game' can be used to find the position of a certain number in a list?
- Good point. I tried to add some transition and tie them in somewhat, but they're still a bit separated. I hope this helps. Deco 07:27, 26 Dec 2004 (UTC)
The pseudocode is pretty intense for me - it seems more complex than it may need to be. I think the number guessing game should include a formula* for finding for finding the smallest number of steps required to resolve any unknown number. [The "50 in 6 steps example" should be accented with a "100 in 7 steps example" to give scope of the power of the algorithm]
- Formula? I can't find the formula or make one - I keep coming up with more code than math [e.g. if NOT real number then]
Real-world programming language example
I would as well appreciate an implementation form in a real-world programming language -- HJH
- Wikipedia isn't a code repository. The pseudocode sufficiently explains the algorithm. Please search and insert an external link. — 131.230.133.185 01:37, 13 July 2005 (UTC)
- At first I was quite alarmed by this change, mostly because the reason used to make the edit could be applied to unilateral deletion of code samples from all articles, which would be very bad and highly controversial. But in this particular case, I believe you're right — the samples are almost identical to the pseudocode in form and function. No need for redundancy. Deco 04:12, 13 July 2005 (UTC)