Scribd Logo
Upload

Welcome to Scribd!

  • 60 views

    Algorithms: DR M Kaykobad Professor CSE Department, BUET

    Uploaded by

    Mahomuda Akter
    Binary search provides a more efficient way to search sorted data compared to sequential search. It works by comparing the search key to the middle element of the array each time, eliminating half of the remaining elements with each comparison. This reduces the average number of comparisons needed from n/2 for sequential search to log2n for binary search. Other efficient search methods include interpolation search for dictionaries and hashing, which maps elements to locations using a hash function.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Algorithms: DR M Kaykobad Professor CSE Department, BUET

    Uploaded by

    Mahomuda Akter
    60 views13 pages
    Binary search provides a more efficient way to search sorted data compared to sequential search. It works by comparing the search key to the middle element of the array each time, eliminating half of the remaining elements with each comparison. This reduces the average number of comparisons needed from n/2 for sequential search to log2n for binary search. Other efficient search methods include interpolation search for dictionaries and hashing, which maps elements to locations using a hash function.

    Original Title

    L1_searching

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Binary search provides a more efficient way to search sorted data compared to sequential search. It works by comparing the search key to the middle element of the array each time, eliminating half of the remaining elements with each comparison. This reduces the average number of comparisons needed from n/2 for sequential search to log2n for binary search. Other efficient search methods include interpolation search for dictionaries and hashing, which maps elements to locations using a hash function.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    60 views13 pages

    Algorithms: DR M Kaykobad Professor CSE Department, BUET

    Uploaded by

    Mahomuda Akter
    Binary search provides a more efficient way to search sorted data compared to sequential search. It works by comparing the search key to the middle element of the array each time, eliminating half of the remaining elements with each comparison. This reduces the average number of comparisons needed from n/2 for sequential search to log2n for binary search. Other efficient search methods include interpolation search for dictionaries and hashing, which maps elements to locations using a hash function.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 13

    Algorithms

    Dr M Kaykobad
    Professor
    CSE Department, BUET
    Searching
    • Most frequent operations in a computer.
    Knuth(Sorting and Searching) says over 25% of
    computer time in 60’s was used in searching.
    • Generally we search for solutions/answers in
    databases or in computation intensive problems.
    • Our shops are arranged to minimize searching
    time, as is the chess board or household goods,
    admission test results or even dictionaries.
    Sequential Search
    When objects are placed in a list sequentially we cannot do
    better than searching it sequentially.
    Sequential_search(A, n, z, index)
    i=1, index=-1
    While i <= n and A(i) ≠ z do
    i++
    enddo
    If i <=n then
    index=i
    endif
    Sequential Search
    • Sequential_search1(A,n,z,index)
    A(n+1)=z, i=1, index=-1
    while A(i) ≠ z do
    i++
    enddo
    If i ≤ n then
    index=i
    endif
    Sequential search complexity
    Best case Worst case Average case

    Successful search 1 n (n+1)/2


    Unsuccessful search n n n

    Best case occurs when the first element is searched,


    worst case when the last is searched. Assuming that
    every element is equally like to be searched. In n
    searches elements are found in all locations requiring
    1+2+…+n=n(n+1) probes. So avg number of probes is
    (n+1)/2. In case of unsuccessful searches all those
    values are equal and equal to n.
    Sequential search complexity
    • In sequential search 1 algorithm i<=n index comparison is not
    required since even if the element were not in the list it has
    been kept at (n+1)st location we are not going to run out of the
    array.
    • However, when n is very large and we need to search out too
    many elements sequential search would be too costly to
    pursue. Imagine had your roll numbers in the successful lists of
    DU admission test or that at BUET appeared in no order how
    difficult would it have been for you to go through the whole list,
    on the average half of it, to find your name or after the list is
    exhausted you come to learn that you are unsuccessful. of w
    Binary search
    To search efficiently we must do much better
    than sequential search although not without
    cost. We must preprocess data as in
    dictionary, maintain some order when stored.
    One way is to keep elements in the sorted
    order. The other one is hashing. Keep an
    element in a location that is a function of the
    element itself.
    Binary search
    Elements are arranged in ascending order. Now the
    element z to be searched out is compared with the
    element in the middle of the array. If z is less then z
    cannot be located to the 2nd half. So we limit our
    search to the first half otherwise to the 2nd.
    Recursively after each probe length of the subfile
    likely to contain z is halved. So if the array contains
    1000 element then 10 probes are good enough, if
    1,000,000 then only 20 probes, if 1,000,000,000
    then only 30.
    Binary search
    • Binary search(A,n,z, index)
    index=-1, low=1, high=n
    while index = -1 and low ≤ high do
    mid=(low+high)/2
    if A(mid)<z then
    low=mid+1
    elseif A(mid)>z then
    high=mid-1
    else
    index=mid
    endif
    enddo
    Finding z in the loop costs a lot, 1.5 comparison per while loop exec . We can delay
    finding z at the end and improve performance as in the next version.
    Binary search
    • Binary search1(A,n,z, index)
    low=1, high=n+1, A(high)=infinity
    while low <high do
    mid=(low+high)/2
    if A(mid)<z then
    low=mid+1
    else
    high=mid
    endif
    enddo
    if A(mid)=z then
    index=mid
    Binary search
    • How do you search an element i such that A(i)=i?
    • How do you search for an element in a bitonic
    sequence?
    • How do you search z equalling sum of an element
    from array X and corresponding element from
    array Y?
    • How do you search an element in a matrix where
    where elements are nondecreasing in rows and
    columns.
    Binary Search complexity
    In the worst case after the full loop has been executed we
    may find the element. This will require ceiling(log 2(n+1))X 2
    comparisons per loop in the worst case. But binary search1
    will take only ceiling(log2(n+1))+1 comparison. For avg
    performance
    1 element can be searched out in 1 comp
    21 2
    22 3
    2(k-1) k
    Assuming n=2k-1 avg number of comp ≈ k-1 ≈ log2n-1
    Other searches
    • Dictionary searching is interpolation search.
    • Hashing is another way of searching efficiently.
    We can store elements at a location that is
    function of the element. Say we want to store
    “dog” we compute location as 4+15+7=26. If
    number of location cannot exceed m then we
    take 26 mod m and store “dog” there if it is
    empty. If not follow some hash collision
    resolution procedure.

    You might also like