'search'에 해당되는 글 2건
- 2016.12.08 [Algorithm] About Linear Search
- 2016.12.08 [Algorithm] About Binary Search Algorithm.
----------------------------------------------------------------------
Hello, i am GameDeveloperPlayground.
I am a Korean student and I post it for English practise.
I would appreciate pointing out grammar or typos.
----------------------------------------------------------------------
In this posting about Linear search.
Linear Search
An alogirthm that searches sequentially from top to bottom.
Time complexity has O(n)
Terminiation condition
If the array find a number in arrays. or if it can not be found until the end, it will be terminiated.
Example Code
1 2 3 4 5 6 7 8 9 10 | int Algorithm(int[] arrays, int target) { for(int i=0; i<arrays.Length; ++i) { if(arrays[i] == target) return i; } return -1; } | cs |
It's simple.
Thank you
'Programing > Algorithm' 카테고리의 다른 글
| [Algorithm] About Select Sort (0) | 2016.12.08 |
|---|---|
| [Algorithm] About Insertion Sort (0) | 2016.12.08 |
| [Algorithm] About Bubble Sort !! (0) | 2016.12.08 |
| [Algorithm] About Binary Search Algorithm. (0) | 2016.12.08 |
| [Algorithm] About Fibonacci sequence (0) | 2016.12.07 |
----------------------------------------------------------------------
Hello, i am GameDeveloperPlayground.
I am a Korean student and I post it for English practise.
I would appreciate pointing out grammar or typos.
----------------------------------------------------------------------
In this post, about Binary search Algorithm.
Binary Search
Data sorting is required to run the binary search algorithm.
Let's look at how algorithm work.
find for number 5 in the array { 1, 3, 4, 5, 7, 8, 10, 20, 60, 100 }.
array[0] | array[1] | array[2] | array[3] | array[4] | array[5] | array[6] | array[7] | array[8] | array[9] |
1 | 3 | 4 | 5 | 7 | 8 | 10 | 20 | 60 | 100 |
First case
Divide array start index and last index value by two.
Check whether the value corresponding to the index is 5 or not if it is 5 or smaller.
( 0 [start index] + 9 [last index] ) /2 = 4.5 (discard the rest) => 4
Since array[4] is = 7. the values not equal.
Array[4] is greater than the value 5. 4~exclude form the dearch until in the list index.
array[0] | array[1] | array[2] | array[3] |
|
|
|
|
|
|
1 | 3 | 4 | 5 |
|
|
|
|
|
|
Second case
(0 [Start index]) + 3 (List index) / 2 = 1.5 => 1
array[1] is 3 , not equal.
array[1] is smaller than 5. it excludes from startindex ~ 1.
|
| array[2] | array[3] |
|
|
|
|
|
|
|
| 4 | 5 |
|
|
|
|
|
|
Third case
(2 [start index]) + 3 [last index] ) /2 = 2.5 => 2
array[2] is 4, not equal.
array[2] is smaller than 5, it excludes from startindex ~2.
|
|
| array[3] |
|
|
|
|
|
|
|
|
| 5 |
|
|
|
|
|
|
Fourth case
(3 [start index]) + 3 [last index]) /2 = 3
array[3] is 5. return the same value index. and end the search.
The time complexity is O(Log N) because retrieve the value by decreasing by half as above.
If the value is not found, return failure value.
Example code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | int searchint(int[] intarrays, int index) { int from = 0; int to = intarrays.Length - 1; while (from <= to) { int mid = (from + to) / 2; if (intarrays[mid] > index) { to = mid - 1; } else if (intarrays[mid] < index) { from = mid + 1; } else { return mid; } } return -1; } | cs |
The terminiation condition of the algorithm.
If the start index(from) is greater than the lst index (to) as in the above code, it terminates.
Thank you.
'Programing > Algorithm' 카테고리의 다른 글
| [Algorithm] About Select Sort (0) | 2016.12.08 |
|---|---|
| [Algorithm] About Insertion Sort (0) | 2016.12.08 |
| [Algorithm] About Bubble Sort !! (0) | 2016.12.08 |
| [Algorithm] About Linear Search (0) | 2016.12.08 |
| [Algorithm] About Fibonacci sequence (0) | 2016.12.07 |
