Verify Binary Search result with duplicate target in the array
1. Notes
Testing scenario: If testArray contains target at position n, then binarySearch (testArray, target) must return n
public void assertTheory4(int[] testArray, int target, int returnValue) { assertEquals(getTargetPosition(testArray, target), returnValue); } public int getTargetPosition(int[] testArray, int target) { for (int i = 0; i < testArray.length; i++) if (testArray[i] == target) return i; return -1; }
Array=[2, 11, 36, 66, 104, 108, 108, 108, 122, 155, 159, 161, 191]
target=108
Binary Search 108 will return 6 while getTargetPosition return 5.
Possible fix
Update the function getTargetPosition to return a int array, which contains all position of the value. Then assert this return int array must contain binary search result.*
Any others?
2. REFERENCE
- SECTION 7.2 OF <BEAUTIFUL CODE>