Skip to Main Content
| Brooklyn College Library & Academic IT |CISC Department

CISC 3130 Data Structures: Searching Algorithms (linear structures)

Professor Chuang Spring 2020 OER

Introduction

An algorithm that solves the search problem retrieving information stored in a data structure.

There are primarily two search algorithms of interest:

1. Linear Search (can be performed on both sorted and unsorted arrays). O(n)

2. Binary Search (requires array to be sorted). O(logn)

Linear Search

Linear search conducts searches in sequential order

O(n)

For i from 0 to n–1
    If i'th element is 50
        Return true
Return false

 

 

 

 

Binary Search

This algorithm is called a binary search because you reduce the search by two (half the size) at every operation.

O(logn)

If no items
    Return false
If middle item is 50
    Return true
Else if 50 < middle item
    Search left half
Else if 50 > middle item
    Search right half

 

 

Creative Commons License NC SA 4.0 icon This OER resource is released under Creative Commons Attribution-Non Commercial-ShareAlike 4.0 International License. It was made for the Spring 2020 semester by Professor Katherine Chuang on Data Structures at Brooklyn College, Department of Computer and Information Science.