Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sequential Search, Cworst, Binary Search - Coggle Diagram
Sequential Search
Sequential Search is a brute force aproach to find an determined element in a list
We can Call this element by K and the problem is find an element smaller than K in a Array called "A"
The Algorithm to find is simple
We just init by the index i = 0 and every loop do i++, this is gonna run until find the A[i] element that we wants
or until the index pass the length of the list, in this case we return -1
The logic of this method is just scroll the entire list until find the element
C
worst
C worst (n) = Cworst (
F
floor(n/2)) + 1 for n > 1, C worst (1) = 1.
Cworst (n) =
F
floor(log 2 n) + 1 =
F
floor(log 2(n + 1)).
C worst (2k ) = k + 1 = log 2 n + 1.
Binary Search
The Binary Search is based on the logic to peak an middle element of the list
If this element be equals a K(The element that we wants) the search stop A[m]
Else we have 2 sublists
The left list that has elements {A[0]...A[m-1]}
if K > A[M] we applies the binary search on this sublist
The rigth has { A[m+1] ... A [n-1]}
If K < A[M] we applies the binary search on this sublist
How many such comparisons does the algorithm make on an array of n elements?
C
avarage
Cavg (n) ≈ log 2 n.