In Programming Pearls (second edition) Column 5, problem 5 the question is about implementing binary search on an unsorted array.

How can you add partial checking to the function at significantly less than O(n-1) cost?

I know you can check with every iteration and achieve O(log n), but the hint in the back suggests there is an O(1) solution.

What is that solution?

**Summary**

Partially checking if the array is sorted so that the binary search is applicable can be done in O(log n), as the OP said, and in O(1). The O(log n) method is to check each of the probes against the previous probe to make sure that it compares properly (less than, greater than). The O(1) method is to just check the final element found by binary search and one next to it so that if the sought-after element wasn't found, at least the correct place for insertion was found. If the sought-after element was found, then that is a good O(1) partial check.

**Longer explanation**

The part of the problem before the code block says that a common problem is using binary search on an unsorted array. Basically, how can use partial checking to check if an array is sorted in less than O(n-1) cost?

The O(log n) solution is to check each of the binary search probes meshes with respect to the previous probe (is less than or greater than it is expected to be). This doesn't guarantee that the array is sorted, but it is a good partial check.

The only O(1) check that I can think of is to check the final place that is searched such that its value and the neighboring values mesh with the idea of where the searched for element should be, even if the element wasn't found. It's a pretty good partial check: if the element is found then things are probably working correctly. If it wasn't, then check the elements around where it should be that such that there is one less than the searched for element and then one that is greater than the searched for element. However, I do realize that checking in this manner means that the binary search, which is O(log n), has already been done so I don't know if this is truly O(1). However, it only adds O(1) to the overall search so I think that it is applicable.

Similar Questions

I have an array of objects (telephone directory entries, stored in the form Entry( surname,initials,extension) ) which I would like to search efficiently. In order to do this I'm trying to use Arrays.

I'm working on a programming assignment and writing a bunch of functions to implement a binary search tree, and some functions are given. I thought I understood recursion, but I keep getting hung up o

In Column 2 of the book Programming Pearls there is a problem asking you to design an algorithm to rotate a string k positions to the left. For example, the string is 12345 and k=2, then the result

I recently wrote a fairly simple piece of code attempting to implement a Binary Search Tree in C with insertion, search, deletion and display operations. Unfortunately, the code does not seem to work.

I have a 2D array which is fully sorted. The arrays below are examples 1 2 3 5 6 7 9 10 11 and 1 2 3 4 5 6 7 8 9 10 I would like to use binary search on these array. Let rows be the number of rows

I want to implement an algorithm that inserts sorted arrays into binary search trees but I don't want ending up with a tree that only grows to one side. Do you have any ideas? Thanks.

Are there any Python built-ins or widely used Python libraries to perform a search in a sorted sequence?

I've been tasked with creating a method that will print all the indices where value x is found in a sorted array. I understand that if we just scanned through the array from 0 to N (length of array)

How to search fast in a non-sorted array? I am unable to think of any other search mechanism apart from linear search. Any pointers will be helpful.

I am making Binary Search Tree and AVL Tree for an assignment. I am having problem when I try to add 1,000,000 elements to Binary Search Tree but I can add key-> value pairs to AVL Tree.(There is n

Hi i have a python related question, I have a sorted Numpy array which i have to find the index of certain values quickly, I've been using a binary search so far but the issue im having is that there

I'm new here and new to Javascript and web programming (I actually know a little bit of Java not for web). So here's the problem I have an array of strings (name of Albums to be more specific) and I a

I am trying to implement binary search in Java: import java.util.Scanner; public class Search { public static void sequential_search(int[] array,int search_variable) { boolean flag = false; for(int lo

Binary research executing usually cause memory leaking problem, although it is faster than linear search. These two search methods, depth first search and binary search, which is more adapted to searc

I was asked the following question in my interview yesterday: Consider a Java or C++ array say X which is sorted and no two elements in it are same. How best can you find an index say i such that elem

can we use write a program in java for binary search using threads. one thread for dividing the array and one for sorting the array.

I'm being asked to display a binary search tree in sorted order. The nodes of the tree contain strings. I'm not exactly sure what the best way is to attack this problem. Should I be traversing the tre

I am trying to implement binary search tree operations and got stuck at deletion. 11 / \ 10 14 Using inorder traversal as representation of tree initially output is 10 11 14. Deleting node 10, outpu

I am trying to write a binary search in f#, but stumbled at a problem: let find(words:string[]) (value:string) = let mutable mid = 0 let mutable fpos = 0 let mutable lpos = words.Length - 1 while fpos

The binary search returns wrong value even though the list is sorted. Here is the list: 1707 ABCD 1707 XXXX 1725 DEFG 1725 HIJK 1725 LMNOP I get this list from a file presorted as per the time (First

I've part of code which is checking input pins of lpt port, but using decimal values: while (PortAccess.Input(889) == 120) How to use this instruction with binary values? for example while bit 3 of 0

I have a sorted String array in Java. I am trying to find the first element which starts with a user specified String in that array. I thought binary search at first, but it finds the equal String not

for a project I need to implement a binary search. This binary search allows duplicates. I have to get all the index values that match my target. I've thought about doing it this way if a duplicate is

I don't know whether the term Lazy Binary Search is valid, but I was going through some old materials and I just wanted to know if anyone can explain the algorithm of a Lazy Binary Search and compar

Suppose an array has been given and want to find element in that array , how can you search an element in that array using binary search and that given array is already sorted and size of the array is

I need to create a function that creates a BST from an array, in python. The array is already sorted. The example is: function array_to_binary_search_tree(array, start, end) if start > end Return a

I want to do a binary search in python: def binarySearch(data, val): Where data is a sorted array and value is the value being searched for. If the value is found, I want to return the index (such th

Someone asked about Lazy Binary Searches today. Not knowing what that was, I looked for it, and found this post: What is Lazy Binary Search? Essentially, a Lazy Binary Search is a Binary Search where

Wrote this to try my hands a building a Binary Search. It is by no means the most refactored code there is but wondering why everything works except when X is the last value in the array (i.e. x = 77)

Binary search can be implemented in many ways-recursive, iterative, conditionals, etc. I took this from Bentley's book Programming pearls: Writing correct programs which is an iterative implementati

how do i represent binary search trees in python?

So I have such problem in Scala, I need to implement binary search with the help of actors, with no loops and recursion, preferably with concurrency between actors. Of course it has no sense, but the

I am currently working on this coding problem for class. Given a sorted array of n distinct values as well as a target value T, determine in O(n) time whether or not there exist two distinct values in

Allright, I'm hoping someone can explain this to me. I'm studying for finals and I can't quite figure something out. The problem is dynamic programming; constructing an optimal binary search tree (OBS

I have a problem with insertion in Binary search tree in C. I have the following definition of a binary tree(please ignore line numbers): 40 struct WordBT 41 { 42 char *term; 43 struct WordBT *right;

Here is a function to convert a binary search tree to sorted doubly linked list.The idea is to do an inorder traversal and put the visited node in a circular array of size 2.The left and right pointer

The requirement is to search an alphabetically ordered/sorted list (of string type) using a binary search method for a specified string (in the example below it is yz) and return the results (every

I am trying to locate the point of rotation in a sorted array through a modified binary search. Consider this array int values[9]={7, 8, 9, 1, 2, 3, 4, 5, 6}; The point of rotation here is at index =

I wonder, can binary search be applied on a 2D array? What would the conditions on the array be? Sorted on 2D?? What would be the time complexity for it? How would the algorithm change the boundary o

i want to implement binary_search with pointers #include <cstdlib> #include <iostream> using namespace std; int binary_p(int x[],int size,int target){ int *p=&x[0]; int *q=&x[size]

Possible Duplicate: What is the difference between Linear search and Binary search? Write a program that generates 20 random integers within the range from 0 to 100. Sort the array in descending or

What is the simplest way to do a binary search on an (already) sorted NSArray? Some potential ways I have spotted so far include: The use of CFArrayBSearchValues (mentioned here) - would this work o

I'm trying to write code for a binary search tree, the first method I'm working on is the add (insert) method. The root seems to insert properly, but I'm getting null pointer exception when adding the

I have a small doubt here... If I know that a search element in a list ,say containing 32 elements sorted in order, is appearing within first four positions, which is the best searching algorithm. Lin

This question already has an answer here: java Arrays.binarySearch fails to find target 3 answers search in a binary tree 2 answers I am trying to search an array for a value and decided to

I am trying to write a Lisp function ordered that returns True if the list it is given is sorted either in ascending or descending order. So far I have 3 helper functions to sort either way, then one

An explanation about Threaded Binary Search Trees (skip it if you know them): We know that in a binary search tree with n nodes, there are n+1 left and right pointers that contain null. In order to us

I was reading through Introduction to algorithms i came across this problem about In-order Traversal of binary search tree without using a stack or recursion. Hint says to assume that testing of point

I have read that std map is implemented using binary search tree data structure. BST is a sequential data structure (like elements in an array) which stores elements in a BST node and maintains elemen

I am trying to optimize a search through a very short sorted array of doubles to locate a bucket a given value belongs to. Assuming the size of the array is 8 doubles, I have come up with the followin