Pengantar Logika : Kerancuan Berpikir dan Jenisnya

Algoritma dan Struktur Data : Searching, Bisection Method, dan Binary Searh The Answer, dan Contoh Soal

Searching in Computer Science

• Table look-up 
• Searching for an optimal solution to a problem 
• String matching: searching for a sub-string in a text 

Table Look-up

Given a table/array of size n, find the value X in the table.

Two approaches: 

• Sequential Search 
• Binary Search

Sequential Search

Sequential search : Brute force method for searching in the table. Brute Force: A straightforward approach to solving a problem, usually directly based on the problem statement and definitions of the concepts involved.

Sequential search : looks at every items in the table/array, stop the process as soon as the value X is found. Guarantees you to find the value, if it is there. A very general (and slow) searching method : T(n) = O(n)

Sequential Search: Running Time

Running Time: 

T(n) = 1+2(n+1)+n+1 = 1+2n+2+n+1 = 3n+4 = O(n)

In line 3, we kept checking against n. Can we avoid that ?

Sequential Search: Sentinel

Running Time: 

T(n) = 1+1+n+1+n+1 

T(n) = 2n+4 = O(n) 

Binary Search

How can we improve the search algorithm ? Exploit special properties of data, e.g: sorted vs unsorted.

Divide-and-Conquer approach : 

• divide the data on the median/medoid 
• check the median 
• decide whether X is found or we can throw one-half of the data

Binary Search: Recursive Version

Binary Search: Running Time

Running time : 

T(1) = 2 

T(n) = 3+T(n/2) 

T(n) = 3+3+T(n/4)=6+T(n/4) 

T(n) = 6+3+T(n/8)=9+T(n/8) 

T(n) = 3i+T(n/2^i ) 

when 2^i=n, i=lg⁡n 

T(n) = 3 lg⁡n+T(1)=3 lg⁡n+2 

T(n) = O(lg⁡n)

Binary Search: Iterative Version

Order Statistics

The i-th order statistic of a set of n elements is the i-th smallest element. Minimum : first order statistic i = 1. Maximum : n-th order statistic i = n

Median : (informally) the "halfway point" of the set 

• if n is odd, median occurs at i=⌊(n+1)/2⌋ 
• if n is even, median occurs at i=⌊(n+1)/2⌋ (lower median) and i=⌈(n+1)/2⌉ (upper median)

Order Statistics: The Selection Problem

Input: A set A of n (distinct) numbers and an integer i, with 1 <= i <= n. 

Output: The element x Є A that is larger than exactly i -1 other elements of A.

Randomized Selection

Randomized Selection: Running Time

Partitioning takes θ (n^2) time

• Worst-case: θ (n^2) : e.g.: Finding the minimum, but pivot always choose the largest element
• Expected : O(n), using random to avoid worst-case behavior and assume that the elements are distinct.

The Bisection Method

The binary search principle can also be used to estimating the root (solution) of a nonlinear equation f (x) = 0. In numerical method, this method is known as The Bisection Method (Bisection: dividing into two equal parts). It works by repeatedly bisects an interval and then selects a sub-interval in which a root must lie for further processing

• Suppose f is a continuos function on the interval [l,r] : 
• if f (l) and f(r) have the same sign, then there may or may not be any root between l and r 
• Gowever, if f(l) and f(r) have opposite sign, then there at least one root between l and r 
• Let’s assume f(l) and f(r) have opposie sign, set m=⌊((l+r))/2⌋ 
• if f(m) = 0, then the root is m 
• if f(m) != 0, then f(m) has the same sign with either f (l) or f (r) 
• if f (m) and f (l) have the same sign, the root is on interval (m, r] 
• if f (m) and f(l) have opposite sign, the root is on interval [l, r) 
• Reapply the process to the new interval 
• On what condition should we stop the process ?

Finding the square root of an integer n : 

• The square root of n is the number s such that s^2=n 
• Observe that the square root of n >= 1 must be at least 1 and at most n 
• Let l = 1 and r = n and consider the midpoint of this interval, m=⌊((l+r))/2⌋ 
• If m^2≤n, then the square root must be greater than m, so the algorithm repeats with l = m 
• If m^2 > n, then the square root must be less than m, so the algorithm repeats with r = m 
• On what condition should we stop the process ? 

Binary Search The Answer

Bisection method can also be used for other type of problems. Assume that the answer (of a particular problem) is on an interval [l,r].

However, trying each answer (to find the right one) can be impossible within limited amount of time. Solution is similar to the bisection method : binary-search the answer (try a middle value, simulate the answer using that value and throw away half of the range)

Condition : the problem should has a special property that can be exploited

Backpacking trails with more than one campsites on its route from start to end-point. Only allowed to camp in the campsite and you know their location in advance. You want to stop (at most) N nights (N+1 days) and minimize the maximum amount of walking in a single day

Example: For 3 days walking, if you walk 10,7,11 (km) each day, the maximum amount is 11. But if you walk : 9,9,10 then the maximum amount is 10 (better than the previous one).

N = 4, Campsites = 7 (6, 3, 5, 7, 2, 4, 3, 5). 

Note: 6 (km) from the start-point to the first campsite. Maximum walk in a day: 8

Sumber

Slide ASD : Searching

http://informatika.unpar.ac.id/