Fundamentals of algorithm

Fundamentals of algorithm

By Ансар Аким

Title: Searching

LO: To use the binary and linear searches to find an item in a list

Computer Science

Draw

Fill the 2D array

​Why do we need searching algorithms?

​Search algorithms prevent you from having to look through lots of data to find the information you are searching for

​A software company is asked to create a program for searching through a database of mobile-phone records for everyone owning a phone in the KZ so that any individual’s number can be retrieved.

​How many records might need to be searched through?

​Binary search

Linear search 

Linear search

How does it work?

A linear search is the simplest method of searching a data set.

Starting at the beginning of the data set, each item of data is examined until a match is made. Once the item is found, the search ends.

If there is no match, the algorithm must deal with this.

A written description algorithm for a linear search might be:

​

1. Find out the length of the data set.

2. Set counter to 0.

3. Examine the value held in the list at the counter position.

4. Check to see if the value at that position matches the value searched for.

5. If it matches, the value is found. Send a message and end the search.

6. If not, increment the counter by 1 and go back to step 3 until there are no more items to search.

7. If all the items have been checked and no match is found, send a message.

​

Multiple Choice

With a data set of 0, 1, 3, 5, 7, 8, 9 how many values would a linear search examine before it found the value 8?

• Zero

• Six

• Five

• Eight

Multiple Choice

A Linear search algorithm requires data to be ordered.

• TRUE

• FALSE

Multiple Choice

What is an advantage of the Linear search algorithm?

• Performs well with small-sized data sets

• Can be used on data sets with more than a million elements

• The fastest searching algorithm

Multiple Choice

What is the disadvantage of the Linear search algorithm?

• It will only work on a sorted data set

• It may be too slow to process large data sets

• Takes more memory t

Home

Open in new tab

Copy link

its time consuming for the enormous arrays

Disadvantages

• With today's powerful computers, small to medium arrays can be searched relatively quickly.

• The list does not need to be sorted.

• Not affected by insertions and deletions.

Advantages

Linear search

Now find 16.

291 46 177 296 34 345 371 214 172 241 151 334 273 376 230 396 302 219 358 144 256 323 339 83 65 85 334 178 8 23 287 399 164 213 83 349 113 295 289 384 338 167 98 99 292 374 93 273 303 346 7 179 64 11 191 241 3 89 277 165 339 247 11 377 261 175 111 29 226 182 234 222 74 176 209 199 25 195 158 69 115 387 170 361 238 376 221 233 240 270 188 77 146 386 47 128 70 73 262 179 68 351 365 87 51 349 46 384 281 371 175 89 96 332 68 77 311 89 394 59 387 78 35 126 41 13 358 394 305 378 14 187 277 193 391 71 267 8 238 393 90 110 1 7 213 307 383 69 123 18 282 163 330 143 85 58 67 27 387 115 331 144 161 218 367 244 233 323 22 41 9 137 29 25 395 279 62 222 396 188 322 56 222 213 306 315 200 94 126 309 355 351 106 211 198 77 296 235 41 102 219 296 376 178 215 143 22 262 335 398 54 305 272 377 16 29 196 1 210 330 81 190 83 221 149 301 236 320 207 340 255 62 65 87 222 136 109 32 391 172 400 244 127 247 388 135 371 258 195 298 191 321 316 401 208 372 372 169 185 268 94 393 233 184 229 1 141 335 284 184 18 119 127 302 142 151 334 309 253 381 376 31 242 264 98 301 78 155 6 378 117 109 330 69 203 70 17 7 8 350 49 197 298 42 178 91 214 368 132 161 247 180 79 15 5 225 325 350 250 115 49 223 131 110 153 64 310 373 212 28 369 86 250 168 258 388 215 281 86 272 236 301 111 68 147 157 293 99 261 105 118 348 350 148 308 180 55 49 139 274 328 328 118 386 224 32 292 163 305 359 359 205 304 398 254 289 250 333 327 98 325 362 245 332 24 47 296 8 149 354 296 322 142 180 256 166 263 396 323 172 91 

Binary search

How does it work?

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item until you've narrowed down the possible locations to just one.

divide and conquer

1. Let min=1 max=N

2. Guess the average of  min and max rounded down so that it is an integer.​

3. If you guessed the number, stop. You found it!

4. If the guess was too low, set min to be one larger than the guess

5. If the guess was too high, set the max to be one smaller than the guess.

6. Go back to step two.

algorithm of Binary search

Here's a step-by-step description of using binary search to play the guessing game:

​

Binary and Linear Search Visualization

You can open this webpage in a new tab.

Copy link

Open in new tab

It’s more complicated than linear search, and is overkill for very small numbers of elements. It works only on lists that are sorted and kept sorted. That is not always feasable, especially if elements are constantly being added to the list.

Disadvantages

• The main advantage of using binary search is that it does not scan each element in the list. Instead of scanning each element, it performs the searching to the half of the list. So, the binary search takes less time to search an element as compared to a linear search.

Advantages

Binary search

Multiple Choice

A binary search is to be performed on the list:

3 5 9 10 23

How many comparisons would it take to find number 9?

• 1

• 2

• 3

• can't find the number 9

Multiple Choice

Describe an advantage of a binary search algorithm

• Data does not need to be in order.

• Performs well over large ordered lists.

• Slow with large data sets.

• Can work on an ordered list.  If unordered must use a linear search.

Binary Search (With Code)

You can open this webpage in a new tab.

Copy link

Open in new tab

Practical work

• Given a 256 item sorted list, what is the maximum number of searches needed to find an item?

• Given a 1000 item sorted list, what is the maximum number of searches needed to find an item?​

Computer Science

Plenary

Give an advantage and a disadvantage of the binary search algorithm.