Lecture02

• 时间复杂度-大O分析
  明确线性查找、二分查找的big-O notation结果及原因
• 8种Java基本数据结构类型（明确String不属于8种基本数据类型)

Programs = Data Structures + Algorithms

• Data Structure:
  --A data structure is an efficient way of storing and organizing data elements / members in the computer memory.
  --The mathematical or logical representation of data in the memory is referred.

DS Objective / Operations

• Objective:
  -- the objective of a data structure is to store, retrieve, and update the data efficiently

• Key operations:
  -- Read / Access: looking up something at a particular spot in DS
  --Search: looking for a particular value / element inside the DS
  --Insert: adding a new value / element into the DS
  --Delete: removing a particular value /element from the DS
  --Update: modifying existing value / element in the DS

• Other operations:
  --Other : Create, Sort, Merge ,Traverse, Destroy

Array: Fundamental Data Structure

• An array is a container object that holds a fixed number of values of a single data type
• The array data type can be:
  --primitive
  --class( stored values will be references!)
• Each item in an array is called an element, and each element is accessed by its numerical index(position)
  *Indexing starts at 0 index

Binary Search

public int binarySearch(int [] array, int key){
int start = 0;
int end = array.length -1;
while(end>=start){
  int middle = (start+end)/2;
if(array[middle] == key){
return middle;
}else if(array[middle]>key){
end = middle -1;
}else{
start = middle +1;
}
}
return -1;
}

Time Complexity Analysis

The Big-Oh Notation

• Running times are often represented using the Big-Oh notation (O(n), for example)
• To estimate the Big-Oh of a function representing a running time, follow these fules:
  -- keep only the dominant term, that is, the term that grows the fastest as n increases.
  --Ignore the coefficient of the dominant term.

Sequential Search: Running Time
Overall time complexity: O(n)