pengertian sarching and sequential search

Searching

Consider searching for a given value v in an array of size N. There are 2 basic approaches: sequential search and binary search.

Sequential Search

Sequential search involves looking at each value in turn (i.e., start with the value in array[0], then array[1], etc). The algorithm quits and returns true if the current value is v; it quits and returns false if it has looked at all of the values in the array without finding v. Here's the code:

    public static boolean sequentialSearch(Object[] A, Object v) {
        for (int k = 0; k < A.length; k++) {
            if (A[k].equals(v)) return true;
        }
        return false;
    }

If the values are in sorted order, then the algorithm can sometimes quit and return false without having to look at all of the values in the array: v is not in the array if the current value is greater than v. Here's the code for this version:

    public static boolean sortedSequentialSearch(Comparable[] A, Comparable v) {
    // precondition: A is sorted (in ascending order)
        for (int k = 0; k < A.length; k++) {
            if (A[k].equals(v)) return true;
        if (A[k].compareTo(v) > 0) return false;
        }
        return false;
    }

The worst-case time for a sequential search is always O(N).

Binary Search

When the values are in sorted order, a better approach than the one given above is to use binary search. The algorithm for binary search starts by looking at the middle item x. If x is equal to v, it quits and returns true. Otherwise, it uses the relative ordering of x and v to eliminate half of the array (if v is less than x, then it can't be stored to the right of x in the array; similarly, if it is greater than x, it can't be stored to the left of x). Once half of the array has been eliminated, the algorithm starts again by looking at the middle item in the remaining half. It quits when it finds v or when the entire array has been eliminated.

Here's the code for binary search:

    public static boolean binarySearch(Comparable[] A, Comparable v) {
    // precondition: A is sorted (in ascending order)
        return binarySearchAux(A, 0, A.length - 1, v);
    }

    private static boolean binarySearchAux(Comparable[] A, int low, int high, int v) {
    // precondition: A is sorted (in ascending order)
    // postcondition: return true iff v is in an element of A in the range
    //                A[low] to A[high]
        if (low > high) return false;
        int middle = (low + high) / 2;
        if (A[middle].equals(v)) return true;
        if (v.compareTo(A[middle]) < 0) {
            // recursively search the left part of the array
            return binarySearchAux(A, low, middle-1, v);
        }
        else {
            // recursively search the right part of the array
            return binarySearchAux(A, middle+1, high, v);
        }
    }


The worst-case time for binary search is proportional to log2 N: the number of times N can be divided in half before there is nothing left. Using big-O notation, this is O(log N). Note that binary search in an array is basically the same as doing a lookup in a perfectly balanced binary-search tree (the root of a balanced BST is the middle value). In both cases, if the current value is not the one we're looking for, we can eliminate half of the remaining values.

terjemahannya ..

Pencarian
Pertimbangkan mencari v nilai yang diberikan dalam sebuah array dari N. Ada 2 pendekatan dasar: pencarian sekuensial dan pencarian biner.
Sequential Search
cari Sequential melibatkan melihat setiap nilai pada gilirannya (yaitu, mulailah dengan nilai dalam array [0], maka array [1], dll). Algoritma berhenti dan mengembalikan true jika nilai sekarang adalah v, tetapi berhenti dan mengembalikan false jika telah melihat semua nilai dalam array tanpa menemukan v. Berikut kode:

    public static boolean sequentialSearch (Object [] A, v Object) {
        for (int k = 0; k A.length <; k + +) {
            jika (. A [k] sama dengan (v)) return true;
        }
        return false;
    }
Jika nilai adalah dalam rangka diurutkan, maka algoritma kadang-kadang bisa berhenti dan kembali palsu tanpa harus melihat semua nilai dalam array: v tidak ada dalam array jika nilai kini lebih besar dari v. Berikut kode untuk ini versi:

    public static boolean sortedSequentialSearch (Sebanding [] A, v Sebanding) {
    / / Prekondisi: A diurutkan (dalam urutan)
        for (int k = 0; k A.length <; k + +) {
            jika (. A [k] sama dengan (v)) return true;
    jika (. A [k] compareTo (v)> 0) return false;
        }
        return false;
    }
Waktu terburuk untuk pencarian sekuensial selalu O (N).
Pencarian biner
Ketika nilai-nilai dalam urutan diurutkan, pendekatan yang lebih baik daripada yang diberikan di atas adalah dengan menggunakan pencarian biner. Algoritma pencarian biner mulai dengan melihat item tengah x. Jika x sama dengan v, itu berhenti dan mengembalikan nilai true. Jika tidak, dia menggunakan relatif pemesanan dari x dan v untuk menghilangkan setengah dari array (jika v kurang dari x, maka tidak dapat disimpan ke kanan dari x dalam array, sama, jika lebih besar dari x, tidak dapat disimpan ke kiri dari x). Setelah setengah dari array telah dieliminasi, algoritma dimulai lagi dengan melihat item yang tengah di babak tersisa. Ia berhenti ketika menemukan v atau ketika seluruh array telah dieliminasi.
Berikut kode untuk pencarian biner:

    public static boolean binarySearch (Sebanding [] A, v Sebanding) {
    / / Prekondisi: A diurutkan (dalam urutan)
        kembali binarySearchAux (A, 0, A.length - 1, v);
    }

    swasta statis boolean binarySearchAux (Sebanding [] A, int low, int tinggi, int v) {
    / / Prekondisi: A diurutkan (dalam urutan)
    / / Postcondition: return v iff sejati adalah dalam elemen dari A dalam kisaran
    / / A [rendah] dengan A [high]
        if (> rendah tinggi) return false;
        int tengah = (rendah + tinggi) / 2;
        jika (. A [tengah] sama (v)) return true;
        if (v.compareTo (A [tengah]) <0) {
            / / Secara rekursif mencari bagian kiri array
            kembali binarySearchAux (A, rendah, menengah-1, v);
        }
        else {
            / / Secara rekursif mencari bagian kanan array
            kembali binarySearchAux (A, tengah +1, tinggi, v);
        }
    }

Waktu terburuk untuk pencarian biner adalah sebanding dengan log2 N: jumlah waktu N dapat dibagi dalam setengah sebelum ada yang tersisa. Menggunakan notasi besar-O, ini adalah O (log N). Perhatikan bahwa pencarian biner dalam array pada dasarnya adalah sama dengan melakukan pencarian di pohon biner seimbang sempurna pencari (akar dari BST seimbang adalah nilai tengah). Dalam kedua kasus, jika nilai sekarang bukan yang kita cari, kita bisa menghilangkan setengah dari nilai-nilai yang tersisa.