I just had the occasion to write the following function, and wondered how the non-commenting folk out there would write or structure this so the comments wouldn't be necessary. The question is a matter of exploring the commenting issues. Here is a delicate piece of code. What are some ways to write it and comment it? Put code only here, put your commentary on BinarySearchCommentary. -- AlistairCockburn ---- ''Alistair's opening C code version, with comments.'' int indexIn (int *Array, int top, int value) { // Given an Array[0..top] of integers, sorted low to high, // Return i such that Array[i] = value, if Array contains value. // Return -1 if value is not in Array. int lower, middle, upper; if top<0 then return( -1 ); lower = 0; upper = top; if ( Array[lower] < value && value < Array[upper] ) then { // Following algorithm is a binary search. // loop invariant: expects and maintains Array[lower] < value < Array[upper] // exits loop when upper = lower + 1. // exits function when Array[middle] = value. // needs separate test for Array[lower]=value, Array[upper]=value. while ( upper > lower + 1 ) { middle = ( upper + lower ) / 2; if Array[middle] == value then return( middle ); if Array[middle] < value then lower = middle else upper = middle; }; // if you got here then never was Array[middle]=value // so Array[lower]=value or Array[upper]=value or value not in Array. if Array[lower] == value then return( lower ); if Array[upper] == value then return( upper ); return( -1 ); ---- ''Alistair revised his algorithm to match Don and Tom's improved and simpler algorithm, O(log log N) faster.'' int binarySearch (int *Array, int top, int target) { // Given a low-to-high sorted Array[0..top], // Return i such that Array[i] = target. // Return -1 if target is not in Array. int lower, middle, upper; lower = 0; upper = top; // loop invariant: if there is actually an i, A[i]=target, // then upper >= i >= lower. Otherwise don't care. // exits function when Array[middle] = value. // must find value using middle, otherwise eventually upper < lower and quit. while ( upper >= lower ) { middle = ( upper + lower ) / 2; if Array[middle] = target then return( middle ); if Array[middle] < target then lower = middle + 1; else upper = middle - 1; }; // never found. return( -1 ); } ---- A little shorter, no-frills C implementation, and one more easily adaptable to generic iterators (as long as it is possible to get the difference between two iterators, and add integers to them). // Search the ascendingly sorted interval [start, end) for value, returning a // pointer to the found element or NULL if the value could not be found // Undefined behaviour if either start or end are invalid pointers, point // to non-integer data or point to non-sorted data ;-) int *binsearch(int *start, int *end, int value) { // Loop while the interval of possible matches is non-empty while (end > start) { int *middle=start+(end-start)/2; if (*middle == value) return middle; if (*middle > value) end=middle; // Value in [start, middle) else start=middle+1; // Value in (middle, end) } return NULL; } -- SimonBrenner ---- ''Don's single-method Smalltalk version (not their preferred version, written for comparison sake).'' presortedAscendingIndexOf: anInteger ifAbsent: aBlock | lowIndex highIndex middleOfRange | lowIndex := 1. highIndex := self size. [lowIndex <= highIndex] whileTrue: [middleOfRange := lowIndex + highIndex // 2. (self at: middleOfRange) == anInteger ifTrue: [^middleOfRange]. anInteger < (self at: middleOfRange) ifTrue: [highIndex := middleOfRange - 1] ifFalse: [lowIndex := middleOfRange + 1]]. ^aBlock value -- DonWells ---- ''XP preferred version is a MethodObject. Written jointly by Don and Tom: '' anArray presortedAscendingIndexOf: anInteger ifAbsent: [-1] Now lets create some unit tests. ((( #( 1 3 5 7 9 11) presortedAscendingIndexOf: 3 ifAbsent: [-1]) == 2) & (( #( 1 3 5 7 9 11) presortedAscendingIndexOf: 2 ifAbsent: [-1]) == -1) & ((#( 1 3 5 7 9) presortedAscendingIndexOf: 9 ifAbsent: [-1]) == 5) & ((#( 1 3 5 7 9 11) presortedAscendingIndexOf: 1 ifAbsent: [-1]) == 1) & ((#( 1 3 5 7 9 11) presortedAscendingIndexOf: 5 ifAbsent: [-1]) == 3) & ((#( 1 3 5 7 9 11) presortedAscendingIndexOf: 0 ifAbsent: [-1]) == -1) & ((#( 1 3) presortedAscendingIndexOf: 2 ifAbsent: [-1]) == -1) & ((#(3) presortedAscendingIndexOf: 2 ifAbsent: [-1]) == -1) & ((#(3) presortedAscendingIndexOf: 3 ifAbsent: [-1]) == 1) & ((#() presortedAscendingIndexOf: 2 ifAbsent: [-1]) == -1)) should return true Now we can create: ''Array methods'' '''presortedAscendingIndexOf: anInteger ifAbsent: aBlock''' ^BinarySearch indexOf: anInteger in: self ifAbsent: aBlock Object subclass: #BinarySearch instanceVariableNames: 'array target notFoundBlock lowIndex highIndex middleOfRange ' classVariableNames: '' poolDictionaries: '' ''BinarySearch class methods'' '''indexOf: anInteger in: anArray ifAbsent: aBlock''' ^(self new setArray: anArray target: anInteger notFoundBlock: aBlock) index ''BinarySearch instance methods'' '''setArray: anArray target: targetInteger notFoundBlock: aBlock ''' array := anArray. target := targetInteger. notFoundBlock := aBlock. lowIndex := 1. highIndex := anArray size ^self '''index''' self doesNotIncludeTarget ifTrue: [^notFoundBlock value]. self isTargetAtMiddleOfRange ifTrue: [^middleOfRange]. self adjustRange. ^self index '''isTargetAtMiddleOfRange''' middleOfRange := lowIndex + highIndex // 2. ^(array at: middleOfRange) == target '''adjustRange''' target < (array at: middleOfRange) ifTrue: [highIndex := middleOfRange - 1] ifFalse: [lowIndex := middleOfRange + 1] '''doesNotIncludeTarget''' ^lowIndex > highIndex -- DonWells and TomKubit ---- ''XP variant on MethodObject not using recursion, from Don: '' index [self doesNotIncludeTarget] whileFalse: [isTargetAtMiddleOfRange ifTrue: [^middleOfRange]. self adjustRange]. ^notFoundBlock value "or if you prefer positive logic replace the first line with-> [self couldStillIncludeTarget] whileTrue:" ---- ''StanSilver offered:'' !Array methodsFor: 'accessing'! '''presortedAscendingIndexOf: anInteger ifAbsent: aBlock''' "Return the index of anInteger in the receiver. Assume the receiver is presorted in ascending order. Use a binary search algorithm for efficiency. If anInteger is not found, return the result of evaluating aBlock. Example usage: #(5 6 7 8) presortedAscendingIndexOf: 7 ifAbsent: [-1] returns 3. #(5 6 7 8) presortedAscendingIndexOf: 9 ifAbsent: [-1] returns -1. " | lowIndex highIndex middleIndex | lowIndex := 1. highIndex := self size. self isEmpty ifTrue: [^ aBlock value]. "Check if empty" (self at: lowIndex) = anInteger ifTrue: [^ lowIndex]. "Check beginning" (self at: highIndex) = anInteger ifTrue: [^ highIndex]. "Check end" [middleIndex := lowIndex + highIndex // 2. "Look at middle index" (self at: middleIndex) = anInteger ifTrue: [^middleIndex]. "Success" (highIndex - lowIndex < 2) ifTrue: [^aBlock value]. "Failure" (self at: middleIndex) > anInteger "Narrow the range" ifTrue: [highIndex := middleIndex] ifFalse: [lowIndex := middleIndex]] repeat "Repeat"! ! ---- ''Sometimes girls just gotta have fun. I felt sure it wasn't necessary to double-check the endpoints. I awarded myself the PropellerBeanie for the following. -- RonJeffries'' ''Array methods'' '''binarySearch: anObject ''' ^self binarySearch: anObject over: (1 to: self size) '''binarySearch: anObject over: anInterval''' | center testValue | anInterval isEmpty ifTrue: [^-1]. center := anInterval center. testValue := self at: center. testValue = anObject ifTrue: [^center]. ^self binarySearch: anObject over: (anObject < testValue ifTrue: [anInterval start to: center - 1] ifFalse: [center + 1 to: anInterval stop]) ''Interval methods'' '''center''' ^start + stop // 2 Or, for minimum lines but not maximum clarity: '''binarySearch: anObject over: anInterval''' anInterval isEmpty ifTrue: [^-1]. (self at: anInterval center) = anObject ifTrue: [^anInterval center]. ^self binarySearch: anObject over: (anObject < (self at: anInterval center) ifTrue: [anInterval start to: anInterval center - 1] ifFalse: [anInterval center + 1 to: anInterval stop]) Source: W.H.Burge, ''Recursive Programming Techniques'', 1975. -- RonJeffries and the C/C++ recursive version: int indexln(int* array, unsigned top, int value) { return indexln(array, 0, top, value); } int indexln(int* array, unsigned lowerIndex, unsigned upperIndex, int targetValue) { if (lowerIndex > upperIndex) { return -1; } unsigned middleIndex = (lowerIndex+upperIndex) / 2; int middleValue = array[middleIndex]; if (middleValue > targetValue) { return indexln(array, lowerIndex, middleIndex-1, targetValue); } else if (middleValue < targetValue) { return indexln(array, middleIndex+1, upperIndex, targetValue); } else { return middleIndex; } } Any good compiler will perform a tail recursion optimisation, so the generated code will be iterative, not recursive. For example (cleaned up for readability only): ; TriCore C compiler v1.1 r1 SN00087771-184 (c) 2000 TASKING, Inc. ; a4 = array ; d4 = lowerIndex ; d5 = upperIndex ; d6 = targetValue ; d2 = result indexln: jge d5,d4,_3 mov d2,#-1 ret ; targetValue not found -- return -1 _3: add d2,d4,d5 sh d2,d2,#-1 ; d2 = middleIndex addsc.a a15,a4,d2,#2 ld.w d15,[a15] ; d15 = middleValue jge d6,d15,_4 addi d5,d2,#-1 ; middleValue > targetValue: repeat with lower half j indexln _4: jge d15,d6,_5 addi d4,d2,#1 ; middleValue < targetValue: repeat with upper half j indexln _5: ret ; Found -- return middleIndex! -- DaveWhipp ---- DaveHarris wants to rename some functions from the DonWells and TomKubit MethodObject version, so that the main routine becomes: '''index''' self isRangeEmpty ifTrue: [^notFoundBlock value]. self isTargetAtMiddleOfRange ifTrue: [^middleOfRange]. self halveRange. ^self index ---- In C, the simplest form would be something like: #include #include static int CompareInt( void *pKey, void *pElement ) { int iKey = *(int *)pKey; int iElement = *(int *)pElement; assert( pKey ); assert( pElement ); if( iKey < iElement ) return -1; else if( iKey == iElement ) return 0; else return 1; } int IndexIn( int *aiSearch, int iSize, int iTarget ) { int *pResult; pResult = (int *)bsearch( &iTarget, aiSearch, iSize, sizeof *aiSearch, CompareInt ); if( !pResult ) return -1; return pResult - aiSearch; } Unless you had some dire need to recreate a library function??!?! I'm guessing you probably don't even need IndexIn if you used bsearch() properly. Why return the index into the array when you can return a pointer to the element? If you can get rid of the function, then you don't '''have''' to comment it! -- SunirShah I just recently wrote a BinarySearch routine that returned both a pointer to the element (or NULL if not found) ''and'' the index in the array (either where the element was found, or where it would be if it was in the array to begin with). That makes it easier to insert the element into the array if it's not already there. -- SeanConner ---- ''LukeGorrie threw in this ErlangLanguage version, possibly years after everyone else had moved on..'' %% Find the index of the term Goal in Tuple. %% Returns: {found, Index} | not_found bsearch(Tuple, Goal) when size(Tuple) >= 1 -> bsearch(Tuple, Goal, 1, size(Tuple)). bsearch(Tuple, Goal, Start, End) -> bsearch(Tuple, Goal, Start, End, middle(Start, End)). bsearch(Tuple, Goal, Start, End, Index) -> Value = element(Index, Tuple), if Value == Goal -> {found, Index}; Start == End -> not_found; Value < Goal -> bsearch(Tuple, Goal, min(Index+1, End), End); Value > Goal -> bsearch(Tuple, Goal, Start, max(Index-1, Start)) end. middle(Start, End) -> trunc(Start + (End - Start) / 2). ---- CommonLisp: ;; It's better than bad, it's LOOP! (defun binary-search (vector item &optional (low 0) (high (1- (length vector)))) (loop for middle = (truncate (+ low high) 2) for middle-obj = (aref vector middle) while (<= low high) if (< middle-obj item) do (setf low (1+ middle)) else if (> middle-obj item) do (setf high (1- middle)) else do (return middle) finally (return nil))) It's funny how similar a recursive solution can look: (defun binary-search (vector x &optional (low 0) (high (1- (length vector)))) (if (> low high) nil (let* ((middle (truncate (+ low high) 2)) (middle-obj (aref vector middle))) (cond ((< middle-obj x) (binary-search vector x (1+ middle) high)) ((> middle-obj x) (binary-search vector x low (1- middle))) (t middle))))) -- TayssirJohnGabbour ---- There is also a BinarySearchInJava