November 7, 2017 10:00 AM
Most implementations of binary search assume that the target array has no duplicates. But sometimes there are duplicates, and in that case you want to find the first occurrence of an item, not just any one of several occurrences. For instance, in the array [1,2,2,3,4,4,4,4,6,6,6,6,6,6,7] the first occurrence of 4 is at element 4 (counting from 0), the first occurrence of 6 is at element 8, and 5 does not appear in the array.
Your task is to write a binary search that finds the first occurrance of a set of duplicate items in a sorted array. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
;; This problem is no different than the usual binary search (dichotomy), ;; but with a modified comparison function. Now, if the current element ;; is equal to the target value, but the previous element is also equal, ;; then the current element must be considered greater. (defun binary-search-first (vector value compare &key (start 0) (end (length vector)) (key (function identity))) " COMPARE: A comparing two elements A and B, and returning an order (signed integer), such as: A<B <=> result<0 A=B <=> result=0 A>B <=> result>0 START: The minimum index. END: The maximum index+1. RETURN: (values found index order) POST: (<= start index (1- end)) +-------------------+----------+-------+----------+ | Case | found | index | order | +-------------------+----------+-------+----------+ | x < a[i] | FALSE | start | less | | a[i] < x < a[i+1] | FALSE | i | greater | | x = a[i] | TRUE | i | equal | | a[max] < x | FALSE | end-1 | greater | +-------------------+----------+-------+----------+ " (com.informatimago.common-lisp.cesarum.utility:dichotomy (lambda (current) (if (= current start) (funcall compare value (funcall key (aref vector current))) (let ((order (funcall compare value (funcall key (aref vector current))))) (if (and (zerop order) (zerop (funcall compare value (funcall key (aref vector (1- current)))))) -1 order)))) start end)) (binary-search-first #(1 2 2 3 4 4 4 4 6 6 6 6 6 6 7) 4 (lambda (a b) (cond ((< a b) -1) ((> a b) +1) (t 0)))) ;; --> t ;; 4 ;; 0By Pascal Bourguignon on November 7, 2017 at 11:02 AM
I would just call the standard binary-search function and then linearly search backwards for the first non-matching value. Granted, if all the values are the same this is O(n), but that isn’t very likely.
By John Cowan on November 7, 2017 at 1:20 PM
@JohnCowan: In the early days of personal computing, I used a shareware database manager that used a standard binary-search function and then scanned backwards, as you suggest. I asked for the first M in a binary F/M field (female/male). You can guess what happened. I sent an email to the developer telling him how to find the first M in logarithmic rather than linear time. He thanked me, and said he had never heard of that before.
By programmingpraxis on November 7, 2017 at 1:40 PM
It’s probably better to skip the equality test in the loop and do a “deferred” check at the end:
def bsearch(a,n): i,j = 0,len(a) # k < i => a[k] < n # k >= j => a[k] >= n while i != j: k = i + (j-i)/2 if a[k] < n: i = k+1 else: j = k return i def find(a,n): k = bsearch(a,n) if k < len(a) and a[k] == n: return k a = [1,2,2,4,4,4,4] print [(i, bsearch(a,i), find(a,i)) for i in range(6)] # [(0, 0, None), (1, 0, 0), (2, 1, 1), (3, 3, None), (4, 3, 3), (5, 7, None)]bsearch returns the index of the first item greater or equal to the given value (or one past the end of the array if there is no such element). find then checks the returned position and returns it if indeed the value is at that position.
By matthew on November 7, 2017 at 6:33 PM
@JohnCowan, your response is consistent with your response to an earlier binary search exercise.
Here’s a related blog post:
https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html
By Daniel on November 7, 2017 at 7:29 PM
I probably should have written:
k = i + (j-i)//2though I think it works as it stands.
By matthew on November 7, 2017 at 8:12 PM
Actually, it doesn’t, integer division is the way to go.
By matthew on November 7, 2017 at 8:15 PM
In fact, in Python 2, int divided by int gives int and the code is OK, in Python 3, it gives a float, but indexing an array with a float gives a runtime error.
By matthew on November 7, 2017 at 8:26 PM
Here’s an O(log n) solution in C99.
#include <stdio.h> int search_dups(int* array, int n, int element) { int lo = 0; int hi = n; int output = -1; while (hi > lo) { int mid = lo + (hi-lo) / 2; int val = array[mid]; if (val < element) { lo = mid + 1; } else if (val > element) { hi = mid; } else { output = mid; hi = mid; } } return output; } int main(void) { int array[] = {1,2,2,3,4,4,4,4,6,6,6,6,6,6,7}; int n = sizeof(array) / sizeof(int); printf("element: index\n"); for (int i = 0; i < 10; ++i) { int idx = search_dups(array, n, i); printf("%d: %2d\n", i, idx); } }Output:
By Daniel on November 7, 2017 at 8:34 PM
In Python this can be easily solved with bisect_left from the bisect module. See the function named “index” in the documentation.
By Paul on November 8, 2017 at 9:01 AM
[…] looked at binary search in the previous exercise. Today we look at ternary search. Instead of one mid at the middle of the array, ternary search has […]
By Ternary Search | Programming Praxis on November 10, 2017 at 10:01 AM
[…] looked at variants of binary search in two recent exercises. Today we look at a third […]
By Floor And Ceiling In An Array | Programming Praxis on November 21, 2017 at 10:01 AM