Let's say we want to write a function in C that finds a specified target value in an unsorted array of ints. In general, this is simple and runs in O(n) time:

```
int search(int *data, int len, int target)
{
int i;
for(i = 0; i < len; i++)
if(data[i]==target) return i;
return -1;
}
```

Let's say we're being masochistic and want to approach this with a divide and conquer algorithm instead. We'll run into trouble on the recursive part because we can't exclude half the array each time, like we can with binary search:

```
int search(int *data, int start, int stop, int target)
{
// Base case: we've divided the array into two size subarray
if(stop==start+1)
{
if(data[start]==target) return start;
if(data[stop]==target) return stop;
return -1;
}
/* The recursion part is tricky.
We *need* to parse both halves of the array, because we can't safely
exclude any part of the array; it's not sorted, so we can't predict
which half it's going to be in.*/
else
{
/** This obviously doesn't work. */
int mid = (stop-start)/2;
return search(data, start, mid, target);
return search(data, mid+1, stop, target);
}
}
```

Is there any way to make this work?

NOTE: This is *not* asking people to do my homework for me, as some of you may think when reading this question. It is, however, inspired by curiosity after I encountered this problem when trying to solve a question in an assignment that I've submitted earlier this week.

I think the answer to your question is no, you can't achieve any benefit using the binary split approach if the data is unsorted.

How about changing the recursive call to:

```
else
{
int mid = (stop-start)/2;
int x = search(data, start, mid, target);
if (x == -1)
return search(data, mid+1, stop, target);
else
return x;
}
```

If the data are not sorted you can not use binary search. But divide and conquer can be used with the following recursive logic (linear search):

```
int search(int *data, int len, int target)
{
if (len == 0)
return -1;
else if (data[0] == target);
return 0;
else
return 1 + search(++data, len-1, target);
}
```

Similar Questions

Assuming we have a large data set in an array (say 50000) and we now want to get the top 50 highest numbers in the array, Would you suggest using a priority queue and pop 50 times? inserting each of t

I am solving Programming Pearls exercises. 4.11 say: Write and prove the correctness of a recursive binary search function in C or C++ with this declaration: int binarysearch(DataType x[], int n);

Possible Duplicate: Make an array to store the calculated numbers in memory I have to modify some code to do some new things. These are the new requirements: -The program will need to use an array i

In an unsorted array, we have to replace every element by the first element to the right that is larger than the current element. If none of the elements to the right are bigger then it should be repl

I'm writing a program in Java where I must implement three search algorithms, among the three is the depth first graph-search algorithm. My program traverses a connected graph represented internally b

Given an unsorted array A = a_1 ... a_n And a set of sorted Arrays B_i = b_i_1 ... b_i_n # for i from 1 to $large_number I would like to find the maximums from the (not yet calculated) sum arrays C_

Binary search algorithm has a big O value of O(log n) and a sequential search has a big O value of O(n). But we need sorting algorithm before a binary search and best big O value for a sorting algotit

The title says it all. I see that I can create a binary search tree out of an unsorted array rather easily. If root is null, set 1st array value to the root current = root for each value in the arra

I am currently coding an algorithm that involving a recursive class. In Matlab, I can put a struct inside a struct, but I wonder if I can do the same thing in C++. For example, I have a square matrix

I'm writing a binary search algorithm using recursion and I just don't know how to start. Here's what I have so far: import javax.swing.*; import java.awt.*; import java.awt.event.*; public class Bina

Problem: I am trying to build a recursive tree using a function and data from a MySQL. However, the results are not as expected. PHP code: function buildTree($root, $next = array()) { // Sanitize inpu

I'm trying to write a search algorithm in C# for a very large project (+700MB) and, due to my lack of experience, my code runs for over 30 hours before it ends/finds error. I'm not asking for anyone t

I'm building a graph editor in Javascript and I need an algorithm to identify all possible routes between two 'node' objects. Given the following JSON object: { failureNode: { failureNode: { fail

I'd like to be able to use php search an array (or better yet, a column of a mysql table) for a particular string. However, my goal is for it to return the string it finds and the number of matching c

I recive 2 strings. I have to implement a recursive function that return the best option for them to be similar by adding -. I give an exemple cause this is not good description str1=sdfsdf str2=df

I'm trying to search a 2d array for a string. The 2d array contains names and birthdays. I want to search a name and display their birthday. When I try to use strcmp to see if the inputted name comp

Ok, so I'm given the function int bin(int value, int size, int array[]) I am supposed to find value within array[], but the issue at hand here is that in most cases, we have something along the

So I have a vector of ints named bList that has information already in it. I have it sorted before running the binary search. //I have already inserted random ints into the vector //Sort it bubbleSort

I'm trying to write an algorithm that will take a list of points visited along an edge, and a list of unvisited edges (made up of pairs of points) which make up the rest of the object and search throu

I have an array of numbers(double) and I want to implement a recursive method in C# to calculate a running average for a given position in the array using the following algorithm: µn+1 = (n * µn)/(n+1

I need to perform a search in two different data structures in C#, and here's the deal: I have one name (which is a string) and I want to perform a search. I have a function called Exists which will r

I have a sorted array of 30 real numbers. The numbers are spread evenly. I want to search a number in this array. Currently, I am using linear search algorithm. In order to increase performance of my

I have string structured like (cat,dog,fish) && (drinks) && (milk,water) I need to convert to an array list like cat drinks milk cat drinks water dog drinks milk dog drinks water fish

I have 2 arrays: $bigArr = array( 'simple'=>1 'advanced'=>array( 'advanceSimple'=>1, 'advanceadvance'=>array( 'simple'=>1 ) ) ) $overide = array( 'advanced'=>array( 'advanceSimple'=&

This problem has been irritating me for too long. I need a non-recursive algorithm in C to generate non-distinct character strings. For instance, if a given character string is 26 characters long, and

I need an Erlang implementation of the A* search algorithm. Any pointers?

Here is another interview question Array contains elements where next element can be either x+1 or x-1 if previous element is x. Prev element = x Next element = x+1/ x-1 Example: {2, 3, 4, 3, 2, 1, 0

I am trying to create a recursive method that uses Horner's algorithm to convert a fractional number in base n to base 10. I've searched here and all over but couldn't find anywhere that dealt with th

Is this possible to find the smallest element of an array of unsorted integers by faster than O (n) time complexity. Space complexity is not a concern.

Working in C#, I would like to write an efficient sorting algorithm that would take as input a text file containing unsorted list of server and path combinations and output a sorted file. As an exerci

I am having a problem with an algorithm I wrote for creating a ascii maze. The code is using a recursive back tracker, and the pseudo code essentially is: 1. Make the initial cell the current cell and

Trying to set up a merge sorting recursive function in C, I came up with the following. The strange behavior is that, when the size of the array is small (around 10), it works perfectly fine. For size

function array_searchRecursive( $needle, $haystack, $strict=false, $path=array() ) { if( !is_array($haystack) ) { return false; } foreach( $haystack as $key => $val ) { if( is_array($val) &&

I am searching for a non-recursive depth first search algorithm on graphs in Pascal (Delphi). I need DFS for computing strongly or bi-connected components of large graphs. Currently I am using a recur

Calling method polymorphic_url in controller or template with array as argument, like: polymorphic_url([@agency, @agency.divisions.first]) causing ArgumentError exception named recursive array joi

Does an algorithm exist that finds the maximum of an unsorted array in O(log n) time?

First of all: this is not a homework assignment, it's for a hobby project of mine. Background: For my Java puzzle game I use a very simple recursive algorithm to check if certain spaces on the 'map' h

task I need a binary search with a homemade algorithm. Now the program should work, but unfortunately this is not the case, he compares it but problem is he charging cities. than those in the output i

The program doesn't output anything currently. The program is meant to take an integer command line value and then print Test that number of times using a recursive printing function. I'm new to C a

I would like to change the value of a recursive array. One array provides the path to the variable to change: $scopePath represents the path to change. For example if $scopePath==Array(owners,produ

How can I create/delete a node in a Binary Search Tree using Iterative Algorithm in C?

I am trying to tackle a classical interview problem which is basically performing a binary search on a list which first increases then decreases. Even though it's obvious that we can achieve O(log n)

This question already has an answer here: Search for a key in an array, recursivly 5 answers I try to find a value in an array, no matter how deep that array is or what structure it may have.

This question already has an answer here: How can I cyclically shift an array without additional heap memory? 2 answers Is there a way to swap two sections of an array without needed to create

Is there an algorithmic approach to find the minimum of an unsorted array in logarithmic time ( O(logn) )? Or is it only possible in linear time? I don't want to go parallel. Thanks Michael

I have a grid with x-sided field in it. Every field contains a link to it's x surrounding fields. [x is constant] I have an algorithm which is implemented in this field, (which can probably be optimiz

I need to find out all the combinations of sum of any two numbers in an array. if it is equal then print them. The linear solution to this problem has O(N^2) complexity. I thought of sorting and then

As you know, the headers_list()-PHP-function returns an array like this: Array ( [0] => Content-type: text/html; charset=utf-8 [1] => key: value [2] => key2: value2 ) In general (or with thi

i want to ask question that how can we search in a plist which is of array type and has elements of array type as well. i am searching from a plist which is of string element type and its working fine

I wanted to ask how lower_bound in cpp ( C++ ) behaves when it is applied on unsorted array. I mean when I ran the following program. #include <iostream> #include<vector> #include<algor