Skip to Main Content
It looks like you're using Internet Explorer 11 or older. This website works best with modern browsers such as the latest versions of Chrome, Firefox, Safari, and Edge. If you continue with this browser, you may see unexpected results.
| 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