Re: Searching in a sorted array

Article View: comp.os.ms-windows.programmer.tools.owl

Article #9

Back to comp.os.ms-windows.programmer.tools.owl Previous Next

From: Paul A. Billings
Date: Mon, 09 Oct 1995 18:14

24 lines
1531 bytes

galor@netvision.net.il (Guy Naor) wrote:
>Hi!!!
>
>I'm looking for the best (fastest) way for finding the first occurence
>of a string in a sorted array, when entries aren't unique. For
>example:
>
>an array containing: AA,AB,AC,AD,BB,BB,BB,BC,BF,CG,CG,CT
>I want to find the first occurance of BB. 
>
>A binary search will stop on the middle BB, and will require a
>backward serial search to find the first BB. Is there a good algorithm
>for this?

Sounds like a binary search followed by a backward serial 
search would be the best! :-)  Seriously, I would use that.  
If, however, you know you have a lot of duplicates, a modified 
binary search could be performed that didn't stop on the first 
occurance of the key.  The problem is that the search "bin" on 
the left of the first key must be exhausted, even if there is 
no duplicate (wasteful).  I would use it ONLY if you know the 
majority of keys are duplicated many times.

Paul

Technical Details

Message-ID: <45boqa$6t0@waena.maui.com>

Path: arc1-ca.pugleaf.net!news.maui.com!news

References: <44prsv$ki7@news.netvision.net.il>

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!news.maui.com!news
From: "Paul A. Billings" <pab@maui.com>
Newsgroups: comp.os.ms-windows.programmer.tools.owl,comp.lang.c++
Subject: Re: Searching in a sorted array
Date: 9 Oct 1995 18:14:34 GMT
Organization: Maui Analysis and Synthesis Technologies
Message-ID: <45boqa$6t0@waena.maui.com>
References: <44prsv$ki7@news.netvision.net.il>
NNTP-Posting-Host: mr9-040.diagsoft.maui.com
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 1.2N (Windows; I; 32bit)
To: galor@netvision.net.il

Reply to Parent Message