Stack Overflow
Stack Overflow

Questions tagged [linear-search]

Linear search or sequential search is a method for finding a particular value in a list, that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found. Linear search is the simplest search algorithm. Its worst case cost is proportional to the number of elements in the list.

280 questions
52
votes
11 answers

What is the difference between Linear search and Binary search?

What is the difference between Linear search and Binary search?
Smi
28
votes
19 answers

How fast can you make linear search?

I'm looking to optimize this linear search: static int linear (const int *arr, int n, int key) { int i = 0; while (i < n) { if (arr [i] >= key) break; ++i; } …
Mark Probst
  • 7,107
  • 7
  • 40
  • 42
9
votes
1 answer

binary search efficiency vs. linear search efficiency in fortran

This question is about the efficiency of a linear search vs. the efficiency of a binary search for a pre-sorted array in contiguous storage... I have an application written in fortran (77!). One frequent operation for my part of the code is to find…
mgilson
  • 300,191
  • 65
  • 633
  • 696
8
votes
2 answers

Optimizing a large if-else branch with binary search

So there is an if-else branch in my program with about 30 if-else statements. This part runs more than 100 times per second, so I saw it as an opportunity to optimize, and made it do binary search with a function pointer array (practically a…
user3810155
8
votes
4 answers

Which is more efficient, Sorting and then Binary Search over a Collection or Linear Search in java

Suppose I am having a Collection of object: List myList = populateMyArrayList(); //Here I am having an ArrayList with 1000 elements Which is the better approach: 1 : Mergesort then Binary Search Collections.sort(myList); int keyIndex =…
Zeeshan
  • 11,851
  • 21
  • 73
  • 98
8
votes
3 answers

How does java.util.Collections.contains() perform faster than a linear search?

I've been fooling around with a bunch of different ways of searching collections, collections of collections, etc. Doing lots of stupid little tests to verify my understanding. Here is one which boggles me (source code further below). In short, I…
The111
  • 5,757
  • 4
  • 39
  • 55
6
votes
1 answer

Can a function return different types depending on conditional statements in the function?

I was wondering if it was possible to return different types depending on the conditions in the function: This code will work if you remove '|| bool' and the 'if/else' statements. Thanks in advance. fn main() { let vector: Vec = vec![0, 2,…
Ranj
  • 718
  • 1
  • 12
  • 19
5
votes
2 answers

average case running time of linear search algorithm

I am trying to derive the average case running time for deterministic linear search algorithm. The algorithm searches an element x in an unsorted array A in the order A[1], A[2], A[3]...A[n]. It stops when it finds the element x or proceeds until it…
Brahadeesh
  • 2,245
  • 8
  • 40
  • 58
5
votes
2 answers

Where to choose linear search over binary search

After having searched the internet I was not able to satisfy myself that I had found a comprehensive set of situations in which a linear search would be preferable to a binary search. I am essentially wondering whether it would be possible to…
user3444063
  • 63
  • 1
  • 1
  • 6
4
votes
1 answer

Why does my binary search run slower than my linear search in MATLAB?

Here is my code for binary search: function result = binarySearch(a, key) binaryFound = false; halfIndex = fix(length(a)/2) + 1; if a(halfIndex) == key binaryFound = true; elseif length(a)==1 && a(1)~=key binaryFound = false; elseif key >…
crimsonprotag
  • 41
  • 1
4
votes
2 answers

C++ Finding the last occurrence of an int in a linear search

This week for homework I've been tasked with loading in a text file of 1,000 numbers and to do a linear search of a number entered in by a user. I have the linear search part done, but I have to find and print the last occurrence of that integer. I…
Justin Farr
  • 183
  • 3
  • 5
  • 16
4
votes
1 answer

IndexError: list index out of range in array search

I'm making a simple program in Python to perform a linear search. But when I run this program it gives me this error: Traceback (most recent call last): File "C:\Users\raj\Documents\EclipseProject\PythonProject1\myProgram.py", line 25, in…
user4834391
  • 55
  • 1
  • 4
4
votes
3 answers

linear search through uint64[] with SSE

i'm trying to implement a linear search through an array of uint64 using SSE instructions. I got things working for uint16 and uint32, but i get compiler errors for the uint64 code (linux, gcc - see specs at the end). I'm trying to compare 2x2 64bit…
cruppstahl
  • 2,447
  • 1
  • 19
  • 25
4
votes
3 answers

Design and analyze a linear time algorithm

Design and analyze a linear time algorithm to determine whether there exists an element in a list of n elements which repeats itself at least n/10 times in the list. How can I do this? I'm posting my own idea as an answer.
starcaller
  • 979
  • 3
  • 16
  • 25
3
votes
3 answers

C++ Linear search algorithm, determining the number of elements in array

This code is from the Geeks for Geeks Algorithms section and i do not understand this part int n = sizeof(arr) / sizeof(arr[0]); In the main function, specifially why the division with sizeof(arr[0]) which would lead to half the number of actual…
Buggorilla
  • 107
  • 1
  • 7
1
2 3
…
18 19