COMS W3134 Lecture Notes - Lecture 1: Linear Search, Binary Search Algorithm
18 Dec 2020
School
Department
Course
Professor
Document Summary
Given array with int s a 121 index a. , decide method to search for a desired value within the array. Simple solution : use linear 1 sequential search. Idea : return - l if not found , return location of first instance public static int linearsearch(int x, int[]a){ int index = -1; Worst case scenario for linear search : (cid:8869: ( n ) item is the last element , when item is not ( we have to go through the entire list ) in the array. Best case scenario : when item is the first ( or one of first ) in array. * in and n are both linear son dominates for average. * in is a constant factor of n so i is not needed. * given that item might not be in array , more often than not we have to go through the entire array.
