If we place our items in an array and sort them in either ascending or descending order on the key first, then we can obtain much better performance with an algorithm called binary search.

**Binary Search**

If we
place our items in an array and sort them in either ascending or descending
order on the key first, then we can obtain much better performance with an
algorithm called **binary** **search**. In binary search, we first
compare the key with the item in the middle position of the** **array. If there's a match, we can return immediately. If the key
is less than the middle key, then the item sought must lie in the lower half of
the array; if it's greater then the item sought must lie in the upper half of
the array. So we repeat the procedure on the lower (or upper) half of the
array.

Our
FindInCollection function can now be implemented:

static
void *bin_search( collection c, int low, int high, void *key ) {

int mid;

/* Termination
check */

if (low
> high) return NULL;

mid =
(high+low)/2;

switch
(memcmp(ItemKey(c->items[mid]),key,c->size)) {

/* Match,
return item found */

case 0:
return c->items[mid];

/* key is
less than mid, search lower half */

case -1:
return bin_search( c, low, mid-1, key);

/* key is
greater than mid, search upper half */

case 1:
return bin_search( c, mid+1, high, key );

default :
return NULL;

}

}

void
*FindInCollection( collection c, void *key ) {

/* Find
an item in a collection

Pre-condition:

c is a
collection created by ConsCollection

c is sorted in ascending order of the key

key !=
NULL

Post-condition:
returns an item identified by key if

one
exists, otherwise returns NULL

*/

int low,
high;

low = 0;
high = c->item_cnt-1;

return bin_search(
c, low, high, key );

}

**Points to note:**

a. bin_search
is recursive: it determines whether the search key lies in the lower or upper
half of the array, then calls itself on the appropriate half.

b. There is
a termination condition (two of them in fact!) i. If low > high then the
partition to be searched has no elements in it *and*

If there
is a match with the element in the middle of the current partition, then we can
return immediately.

c.
AddToCollection will need to be modified to ensure that each item added is
placed in its correct place in the array.

The
procedure is simple:

i. Search
the array until the correct spot to insert the new item is found,

ii. Move all
the following items up one position *and*

iii. Insert
the new item into the empty position thus created.

bin_search
is declared static. It is a local function and is not used outside this class:
if it were not declared static, it would be exported and be available to all
parts of the program. The static declaration also allows other classes to use
the same name internally.

A
technique for searching an ordered list in which we first check the middle item
and – based on that comparison - "discard" half the data. The same
procedure is then applied to the remaining half until a match is found or there
are no more items left.

**1. Characteristics**

The worst
case performance scenario for a linear search is that it needs to loop through
the entire collection; either because the item is the last one, or because the
item isn't found. In other words, if you have *N* items in your collection, the worst case scenario to find an item
is *N* iterations. This is known as *O(N)* using the Big O Notation. The speed
of search grows linearly with the number of items within your collection.
Linear searches don't require the collection to be sorted. In some cases,
you'll know ahead of time that some items will be disproportionally searched
for. In such situations, frequently requested items can be kept at the start of
the collection. This can result in exceptional performance, regardless of size,
for these frequently requested items.

Linear
Search 1 Problem:

Given a
list of N values, determine whether a given value X occurs in the list. 1 2 3 4
5 6 7 8 17 31 9 73 55 12 19 7

For
example, consider the problem of determining whether the value 55 occurs in:
There is an obvious, correct algorithm:

start at
one end of the list, if the current element doesn't equal the search target,

move to
the next element, stopping when a match is found or the opposite end of the
list is reached.

Basic
principle: divide the list into the current element and everything before (or
after) it;

if
current isn't a match, search the other case algorithm Linear Search takes
number X, list number L, number Sz

# Determines
whether the value X occurs within the list L.

# Pre: L
must be initialized to hold exactly Sz values

## Walk
from the upper end of the list toward the lower end,

# looking
for a match:

while

Sz > 0
AND L[Sz] != X Sz := Sz - 1

endwhile
if Sz > 0

# See if we
walked off the front of the list display true

# if so, no
match else display false

if not,
got a match

Halt

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Object Oriented Programming and Data Structure : Sorting And Searching : Binary Search |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.