Scribd
Upload
2 views3 pages

Searching Algorithms

This document provides an overview of searching algorithms, focusing on linear and binary search methods for arrays. It outlines the implementation of binary search in various programming languages and categorizes problems into easy, medium, and hard levels related to searching. Additionally, it mentions other searching algorithms such as sentinel linear search, ternary search, and jump search.

Uploaded by

saraladosuri
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views3 pages

Searching Algorithms

This document provides an overview of searching algorithms, focusing on linear and binary search methods for arrays. It outlines the implementation of binary search in various programming languages and categorizes problems into easy, medium, and hard levels related to searching. Additionally, it mentions other searching algorithms such as sentinel linear search, ternary search, and jump search.

Uploaded by

saraladosuri
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Searching algorithms are essential tools in computer science used to

locate specific items within a collection of data. In this tutorial, we are


mainly going to focus upon searching in an array. When we search an item
in an array, there are two most common algorithms used based on the
type of input array.

 Linear Search : It is used for an unsorted array. It mainly does one


by one comparison of the item to be search with array elements. It
takes linear or O(n) Time.

 Binary Search : It is used for a sorted array. It mainly compares the


array's middle element first and if the middle element is same as
input, then it returns. Otherwise it searches in either left half or right
half based on comparison result (Whether the mid element is
smaller or greater). This algorithm is faster than linear search and
takes O(Log n) time.

Basics

 Introduction

Binary Search Implementations

 binary_search, lower_bound and upper_bound in C++

 [Link]() in Java

 [Link]() in Java for Search in subarray

 [Link]() in Java

 Bisect in Python

 [Link] in C#

Easy Problems

 Largest in an Array

 Second Largest in an array

 Largest three in an array

 Missing Number

 First Repeating

 Missing and Repeating

 Count 1’s in a sorted binary array

 k largest(or smallest) Elements

 Kth smallest in row and column-wise sorted


 Common elements in 3 sorted

 Ceiling & Floor in a Sorted

 Max in a Bitonic

 More than n/k times Appearing

Medium Problems

 Triplets with zero sum

 Partition Point

 Largest pair sum

 K’th Smallest in Unsorted Array

 Search, Min & Max in a Sorted & Rotated

 Peak element

 Fixed Point

 K Most Frequent

 K Closest

 Binary Search for Rationals

 Missing in AP

Hard Problems

 Median of two sorted of same sizes

 Median of two sorted of different sizes

 Search in an almost sorted

 Search in a sorted infinite

 Pair sum in a sorted and rotated

 K’th Smallest/Largest in Unsorted

 K’th largest in a stream

More Searching Algorithms

 Sentinel Linear Search

 Meta Binary Search

 Ternary Search

 Jump Search
 Interpolation Search

 Exponential Search

 Fibonacci Search

 Best First Search (Informed Search)

You might also like