Statement of the unsorted list search problem:

Given a list A = (a1, a2, , ai,, an) of unsorted distinct items and a value k.

It is necessary:

- to find and return index i, such that k = ai, if k A;

- to return index -1, if k A;

In memory a list is represented by an array of integer elements.

A natural idea for an unsorted list search algorithm is as follows:

Compare each item of A to k in some sequence until ai = k is found or the last item in A was examined.

This idea follows the guidelines of the brute force method of algorithm design:

Use a simple, straightforward procedure to try each option that might bring a solution to the problem. This technique relies heavily on huge speed and memory of computers.

Problems to be solved by yourselves: (further details at the end)

Searching unsorted array with duplicate data items.

Given array int B[10] = {10, 70, 20, 30, 25, 70 , 10, 25, 70, 50};

Design algorithm int SearchUnsorted_First(int L[], int n, int k) that finds and returns the index of the first occurrence of k in L. If k is not found, -1 is returned. For example, the call SearchUnsorted_First(B, 10, 70); should return 1 (index of the first occurrence of 70 in the above array B).

The call: SearchUnsorted_First(B, 10, 15); should return -1.

Design algorithm int SearchUnsorted_L(int L[], int n, int k) that finds and returns the index of the last occurrence of k in L. If k is not found, -1 is returned. For example, the call SearchUnsorted_L(B, 10, 70); should return 8 (index of the last occurrence of 70 in the above array B).

The call: SearchUnsorted_L(B, 10, 20); should return 2.

Searching sequentially a sorted array without duplicate items.

Design algorithm int SearchSorted_Asc(int L[], int n, int k) that finds and returns the index of k in L sorted in ascending order. If k is not found, -1 is returned. For example, given array int C[10] = {20, 30, 40, 50, 60, 70 , 80, 90, 100, 110}; sorted in ascending order. The call SearchSorted_ Asc (C, 10, 70); should return 5 (index of 70 in the above array C).

The call: SearchSorted_ Asc (C, 10, 35); should return -1(not found).

Design algorithm int SearchSorted_Des(int L[], int n, int k) that finds and returns the index of k in L sorted in descending order. If k is not found, -1 is returned. For example, given array int D[12] = {120, 110, 100, 90, 80, 70 , 60, 50, 40, 30, 20, 10}; sorted in descending order. The call SearchSorted_ Dec(D, 10, 90); should return 3 (index of 90 in the above array D).

The call: SearchSorted_ Dec(D, 10, 115); should return -1(not found).

Note: in 3.1 and 3.2 algorithms, the search should be terminated if the remaining part of the array cannot contain a target key.

Searching sequentially a sorted array with duplicate items.

Design algorithm int SearchSorted_Asc_Du(int L[], int n, int k) that finds and returns the index of the first occurrence of k in L sorted in ascending order. If k is not found, -1 is returned. For example, given array int F[10] = {20, 30, 30, 50, 60, 60 , 60, 90, 100, 110}; sorted in ascending order. The call SearchSorted_ Asc_Du(F, 10, 60); should return 4 (index of the first occurrence of 60 in the above array F).

The call: SearchSorted_ Asc_Du (F, 10, 55); should return -1(not found).

Design algorithm int SearchSorted_Des_Du(int L[], int n, int k) that finds and returns the index of the last occurrence of k in L sorted in descending order. If k is not found, -1 is returned. For example, given array int G[12] = {120, 110, 110, 110, 80, 70 , 70, 50, 40, 30, 30, 30}; sorted in descending order. The call SearchSorted_ Dec_Du(G, 12, 70); should return 6 (index of the last occurrence of 90 in the above array G).

The call: SearchSorted_ Dec_Du(G, 12, 10); should return -1(not found).

Note: in 4.1 and 4.2 algorithms, the search should be terminated if the remaining part of the array cannot contain a target key.

Binary search in a sorted array without duplicate items.

Design algorithm int BinarySearch_Asc(int L[], int n, int k) that finds and returns the index of k in L sorted in ascending order. If k is not found, -1 is returned. For example, given array

int C[10] = {20, 30, 40, 50, 60, 70 , 80, 90, 100, 110}; sorted in ascending order. The call : BinarySearch_ Asc (C, 10, 70); should return 5 (index of 70 in the above array C).

The call: BinarySearch_ Asc (C, 10, 25); should return -1(not found).

Design algorithm int BinarySearch_Des(int L[], int n, int k) that finds and returns the index of k in L sorted in descending order. If k is not found, -1 is returned. For example, given array

int D[12] = {120, 110, 100, 90, 80, 70 , 60, 50, 40, 30, 20, 10}; sorted in desscending order. The call: BinarySearch_ Asc (D, 12, 70); should return 5 (index of 70 in the above array D).

The call: BinarySearch_ Asc (D, 12, 25); should return -1(not found).